Disjoint Set Test

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const int INF = 0x3f3f3f3f; //❄️
    5vector<int> parent, rk;
    6int find(int x) {
    7    if(parent[x] == x) return x;
    8    return parent[x] = find(parent[x]);
    9}
    10void unite(int x, int y){
    11    x = find(x); y = find(y);
    12    if (rk[x] > rk[y]) {
    13        parent[y] = x;
    14    } else if(rk[y] > rk[x]) {
    15        parent[y] = x;
    16    } else {
    17        parent[y] = x;
    18        rk[x]++;
    19    }
    20}
    21int main() {
    22    ios::sync_with_stdio(0); cin.tie(0); 
    23    int n, m; cin >> n >> m;
    24    vector<pair<int, int>> edge;
    25    parent.resize(n + 1); rk.resize(n + 1);
    26    for (int i = 0; i < parent.size(); i++) parent[i] = i;
    27    for (int i =  0; i < m; i++) { 
    28        int u, v; cin >> u >> v;
    29        edge.emplace_back(u, v);
    30    }
    31    vector<int> ans;
    32    int cnt = 0;
    33    for(int i = 0; i < m; i++) {
    34        auto[x, y] = edge[i];
    35        if (find(x) != find(y)) {
    36            cnt++;
    37            unite(x, y);
    38            ans.push_back(i + 1);
    39        }
    40        if (cnt == n - 1) break;
    41    }
    42    if(cnt < n - 1){
    43        cout << "Disconnected Graph" << '\n';
    44        return 0;
    45    }
    46    for (int i = 0; i < ans.size(); i++) cout << ans[i] << "\n";
    47    return 0;
    48}