PAT A급 1107 Social Clusters(30점)(및 조회)

제목 설명: 전송문
사고방식: 제목에서 두 사람이 임의로 같은 취미를 가지면 그들은 한 조로 나눌 수 있기 때문에 각 취미에 대응하는 사람을 기록할 수 있다. (취미는 여러 사람에게 대응할 수 있지만 여기에 마음대로 기록하면 된다. 있으면 나중에 합병할 수 있다) 그 다음에 모든 사람의 흥미를 두루 훑어보고 취미에 대응하는 사람에 따라 합병하면 된다. 구체적으로 코드를 참고하자.
코드:

#include 

using namespace std;

const int maxn = 1005;

int ans[maxn];
int cnt[maxn];
int p[maxn];
vector <int> v[maxn];

int mfind(int u) {
	return p[u] == u ? u : p[u] = mfind(p[u]);
}

int main() {
	int n;
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; i++)p[i] = i;
	for(int i = 1 ; i <= n ; i++) {
		int t;
		scanf("%d:" , &t);
		while(t--) {
			int num;
			scanf("%d" , &num);
			cnt[num] = i;
			v[i].push_back(num);
		}
	}
    for(int i = 1 ; i <= n ; i++) {
		for(int j = 0 ; j < v[i].size() ; j++) {
			int x = cnt[v[i][j]]; x = mfind(x);
			int y = mfind(i);
			if(x != y) {
				p[x] = y;
				
			}
			
		}
	}
	int res = 0;
	for(int i = 1 ; i <= n ; i++) {
		int u = mfind(i);
		if(!ans[u])res++;
		ans[u]++;
	}
	sort(ans + 1 , ans + n + 1 );
	printf("%d
" , res);
	for(int i = n ; i >= n - res + 1 ; i--) {
		if(i < n)printf(" ");
		printf("%d" , ans[i]);
	}
	printf("
");
	return 0;
}