1107. Social Clusters 解析

本文主要是介绍1107. Social Clusters 解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

兴趣圈，并查集的问题。

把爱好用并查集来处理，处理完了，再将人按爱好进行分类。统计。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>#define MAX 1010using namespace std;int hobbie[MAX];
set <int> cluster;
set <int> h;
int n;
int c[MAX];struct people {vector <int> hobbie;
};
people p[MAX];void Init() {for (int i = 0; i < MAX; i++) {hobbie[i] = i;}
}void Compress(int n,int top) {if (hobbie[n] != top) {Compress(hobbie[n], top);hobbie[n] = top;}
}int Find(int n) {if (hobbie[n] != n) {int top = Find(hobbie[n]);Compress(n, top);}return hobbie[n];
}void Union(int n1, int n2) {int a = Find(n1);int b = Find(n2);
//	cout << n1 << " " << a << " || " << n2 << " " << b << endl;if (a != b) {hobbie[a] = b;
//		cout << a << " -> " << b << endl;}
}bool cmp(int n1, int n2) {return n1 > n2;
}int main() {cin >> n;Init();memset(c, 0, sizeof(c));int times, temp;for (int i = 0; i < n; i++) {cin >> times;cin.get();int head;cin >> head;p[i].hobbie.push_back(head);h.insert(head);for (int j = 1; j < times; j++) {cin >> temp;p[i].hobbie.push_back(temp);h.insert(temp);Union(head, temp);head = Find(temp);}}set <int>::iterator it;for (it = h.begin(); it != h.end(); it++) {cluster.insert(Find(*it));}for (int i = 0; i < n; i++) {c[Find(p[i].hobbie[0])]++;}sort(c, c + MAX, cmp);cout << cluster.size() << endl;cout << c[0];for (int i = 1; i < cluster.size(); i++) {cout << " " << c[i];}cout << endl;return 0;}

这篇关于1107. Social Clusters 解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---