并查集

使用路径压缩维护集合。输入 n、m，再输入 m 对合并节点，最后输出每个节点的代表元。

#include <bits/stdc++.h>
using namespace std;

vector<int> fa;
int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
int main() {
    int n,m; cin >> n >> m;
    fa.resize(n+1); iota(fa.begin(),fa.end(),0);
    while(m--) { int child,parent; cin >> child >> parent; fa[find(child)]=find(parent); }
    for(int i=1;i<=n;++i) cout << find(i) << (i==n?'\n':' ');
}