[C++] PAT 1107 Social Clusters (30分)

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

题解：

该题考察查并集，
1.建立一个course[],course[t]代表第一个选择课程t的人
2.建立father[],
3.进行输入,对于每个人i,若其选择的course[t]==0,则将其赋值给course[t],否则修改其father，使其与course[t]的father相等
4.再次遍历所有人，更新root[father[i]]的值，最后输出

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;

vector<int> father,root;
int course[1010]={0};
int ans_num=0;


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[a] = x;
	}


	return x;

}


void cluster(int a,int b){
	int faA = findFather(a);
	int faB = findFather(b);
	if(faA != faB){
		father[faA] = faB;
	}

}


int main(){
	cin >> n;
	father.resize(n+1);
	root.resize(n+1);

	for(int i=1;i<=n;i++){
		father[i] = i;
	}

	for(int i=1;i<=n;i++){
		int temp;
		scanf_s("%d: ",&temp);
		int temp_course;
		for(int j=0;j<temp;j++){
			cin >> temp_course;
			if(course[temp_course] == 0){
				course[temp_course] = i;
			}
			cluster(i,findFather(course[temp_course]));

		}
	}

	for(int i=1;i<=n;i++){
		root[findFather(i)]++;
	}

	for(int i=1;i<=n;i++){
		if(root[i] != 0){
			ans_num++;
		}
	}
	
	sort(root.begin(),root.end(),cmp);

	cout << ans_num << endl;
	
	for(int i=0;i<ans_num;i++){
	  cout << root[i];
	  if(i != ans_num -1 ){
		cout << " ";
	  }
	
	}


	system("pause");
	return 0;
}