42 lines
660 B
C++
42 lines
660 B
C++
//并查集 + 链表
|
|
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
|
|
vector<int> parent;
|
|
|
|
int find(int x){
|
|
if(parent[x] != x) parent[x] = find(parent[x]);
|
|
return parent[x];
|
|
}
|
|
void merge(int x, int y){
|
|
auto ax = find(x);
|
|
auto ay = find(y);
|
|
|
|
if(ax != ay) parent[ax] = ay;
|
|
}
|
|
|
|
int main(){
|
|
int t;
|
|
cin >> t;
|
|
for(int i = 0; i < t; i++){
|
|
parent.clear();
|
|
int n, m;
|
|
cin >> n >> m;
|
|
parent.resize(n);
|
|
for(int j = 0; j < n; j++){
|
|
parent[j] = j;
|
|
}
|
|
for(int j = 0; j < m; j++){
|
|
int a, b;
|
|
cin >> a >> b;
|
|
merge(a - 1, b - 1);
|
|
}
|
|
for(int j = 0; j < n; j++){
|
|
cout << find(j) + 1 << " ";
|
|
}
|
|
cout << endl;
|
|
}
|
|
|
|
return 0;
|
|
} |