一、题目描述
原题链接 When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A social cluster is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.
Input Specification:
Output Specification:
Sample Input:
8 3: 2 7 10 1: 4 2: 5 3 1: 4 1: 3 1: 4 4: 6 8 1 5 1: 4
Sample Output:
3 4 3 1
二、解题思路
并查集的题目，这道题最重要的是把题读懂，每个人有不同的爱好，有着相同爱好的人自然可以形成一个cluster，当然，拥有不同爱好的人如果有一个共同的朋友，则他们也属于同一个cluster。基于这个，我们就可以按照爱好来进行并查集的操作，能够相连的爱好，我们把它们的根设为同一个，那么我们就可以遍历所有的人，看他的第一个爱好的根结点，使cnt数组对应自增即可。建立一个set用于存放不同的爱好对应cluster的根，遍历这个set，将cnt数组对应的数存入ans中，随后从大到小排序，遍历输出即可。
三、AC代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std
;
const int maxn
= 1010;
int father
[maxn
], cnt
[maxn
] = {0};
vector
<vector
<int> > people
;
bool cmp(int a
, int b
)
{
return a
> b
;
}
int findFather(int x
)
{
int a
= x
;
while(x
!= father
[x
]) x
= father
[x
];
while(a
!= father
[a
])
{
int z
= a
;
a
= father
[a
];
father
[z
] = x
;
}
return x
;
}
void Union(int a
, int b
)
{
int faA
=findFather(a
), faB
= findFather(b
);
father
[faA
] = faB
;
}
int main()
{
int N
, K
, id
, tmp
;
for(int i
=0; i
<maxn
; i
++) father
[i
] = i
;
scanf("%d", &N
);
people
.resize(N
);
for(int i
=0; i
<N
; i
++)
{
scanf("%d: %d", &K
, &id
);
people
[i
].push_back(id
);
for(int j
=1; j
<K
; j
++)
{
scanf("%d", &tmp
);
Union(id
, tmp
);
people
[i
].push_back(tmp
);
}
}
set
<int> clusters
;
vector
<int> ans
;
for(int i
=0; i
<N
; i
++)
{
int root
= findFather(people
[i
][0]);
clusters
.insert(root
);
cnt
[root
]++;
}
for(set
<int>::iterator it
= clusters
.begin(); it
!=clusters
.end(); it
++)
{
ans
.push_back(cnt
[*it
]);
}
sort(ans
.begin(), ans
.end(), cmp
);
printf("%d\n", clusters
.size());
for(int i
=0; i
<ans
.size(); i
++)
i
== 0 ? printf("%d", ans
[i
]) : printf(" %d", ans
[i
]);
return 0;
}
