不是并查集就完事了么,可能一个坑点在有序输出吧
变量名不要在意哈,随便起🤣orz
#include <bits/stdc++.h> using namespace std; const int Max = 10000 + 10; int n,m; int pre[Max],People[Max]; int find(int x){ while(x != pre[x]) x = pre[x]; return x; } void Union(int x,int y){ x = find(x); y = find(y); if(x!=y) pre[y] = x; } int main(){ cin >> n >> m; int a,b; for(int i = 1; i <= n; i++) pre[i] = i; while(m--){ cin >> a >> b; Union(a,b); } for(int i = 1; i <= n; i++) People[i] = 0; int k; map<int, vector<int>> res; for(int i = 1; i <= n; i++){ k = find(i); res[k].push_back(i); } cout << res.size() << endl; map<int, vector<int> >::iterator iter = res.begin(); vector<vector<int> > t; while(iter != res.end()) { vector<int> v = iter->second; vector<int> temp; for(int i = 0; i < v.size(); i++){ temp.push_back(v[i]); } t.push_back(temp); iter++; } sort(t.begin(), t.end()); for (vector<vector<int>>::iterator it = t.begin(); it != t.end(); ++it){ for (int i = 0; i < (*it).size(); ++i) cout << (*it)[i] << " "; cout << endl; } return 0; }
全部评论
(3) 回帖