---
# System prepended metadata

title: Disjoint set
tags: [Algorithm]

---

Disjoint set
===
###### tags: `Algorithm`

```cpp
#define _for(i,a,b) for(int i=(a);(i)<(b);(i)++)
#define MAXN 100010 
#include <iostream>
#include <cstdio>
using namespace std;

int p[MAXN]; 

int parent(int x) {
    if (p[x] == x) return x;
    p[x] = parent(p[x]);
    return p[x];
}

int main() {
    int T; cin >> T; while (T--)
    {
        int N, M; cin >> N >> M;
        _for(i, 1, N+1)    p[i] = i;
        _for(i, 0, M) {
            int a, b; cin >> a >> b;
            p[parent(b)] = a;
        }
        _for(i, 1, N+1) cout<<parent(i)<<'\n';
    }

    return 0;
}
```