并查集
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <cstdio>
#include <vector>
#include<algorithm>
using namespace std;
#define N 1002
int isRoot[N] = { 0 }, father[N];
vector<int>hobbies[N];
int findFather(int v) {
int a = v;
while (father[v] != v)v = father[v];
while (father[a] != v) {
int z = father[a];
father[a] = v;
a = z;
}
return v;
}
void merge(int a, int b) {
int u = findFather(a);
int v = findFather(b);
if (u != v)father[u] = v;
}
bool ifmerge(int a, int b) {
int flag = false;
for (int i = 0;i < hobbies[a].size();i++)
for (int j = 0;j < hobbies[b].size();j++) {
if (hobbies[a][i] == hobbies[b][j])flag = true;
}
return flag;
}
bool cmp(int a, int b) {
return a > b;
}
int main() {
int n, i, j;
scanf("%d", &n);
int thobby, numhobby;
for (i = 1;i <= n;i++) {
scanf("%d: ", &numhobby);
for (j = 0;j < numhobby;j++) {
scanf("%d", &thobby);
hobbies[i].push_back(thobby);
}
}
for (i = 1;i <= n;i++)
father[i] = i;
for (i = 1;i < n;i++) {
for (j = i + 1;j <= n;j++) {
if(ifmerge(i, j))
merge(i, j);
}
}
for (i = 1;i <= n;i++)
isRoot[findFather(i)]++;
int numcluster = 0;
for (i = 1;i <= n;i++)
if (isRoot[i] != 0)numcluster++;
printf("%d\n", numcluster);
sort(isRoot, isRoot + n + 1, cmp);
if (isRoot[0] != 0)printf("%d", isRoot[0]);
i = 1;
while (isRoot[i] != 0) {
printf(" %d", isRoot[i]);
i++;
}
return 0;
}
另
对比柳神的代码，发现爱好不需要用vector数组存起来，可以输入一个处理一个。即：
用course[t]表示任意一个喜欢t活动的人的编号。
如果当前的活动t之前没有人喜欢过（course[t]==0），那么就course[t] = i，i为它自己的编号，表示i为喜欢course[t]的一个人的编号。如果t之前有人喜欢过了，那么就让i和喜欢这个活动的人（即course[t]）处在同一个社交圈里， 即Union(i, findFather(course[t]))。
代码实现如下：
for(int i = 1; i <= n; i++) {
scanf("%d:", &k);
for(int j = 0; j < k; j++) {
scanf("%d", &t);
if(course[t] == 0)
course[t] = i;
else Union(i, course[t]);
}
}
