不是并查集就完事了么,可能一个坑点在有序输出吧
变量名不要在意哈,随便起🤣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) 回帖