Submission

Score: 0

User: KantaponZ

Problemset: Tech Sprites

Language: cpp

Time: 0.740 second

Submitted On: 2025-06-10 22:32:41

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

int n, m, ct = 0;
int pa[1000001];
int num[1000001];
map<pair<int,int>,int> ab;
queue<int> order;

int find_pa(int n) {
    if (pa[n] == n) {
        return n;
    }
    return pa[n] = find_pa(pa[n]);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        pa[i] = i;
        num[i] = 1;
        int a, b;
        cin >> a >> b;
        ab[{a, b}] = i;
    }
    for (auto [x, i] : ab) {
        cout << i << " ";
        order.push(i);
    }
    while (m--) {
        int u, v;
        //cin >> u >> v;
        int pu = find_pa(u), pv = find_pa(v);
        if (pu != pv) {
            num[pu] += num[pv];
            pa[pu] = pv;
        }
    }
//cout << endl;
/*
    for (int i = 1; i <= n; i++) {
        cout << num[i] << " ";
    }*/

    int ct = 0;
    int prev = order.front();
    while (!order.empty()) {
        int x = order.front();
        order.pop();
        int px = find_pa(x), pp = find_pa(prev);
        if (px != pp && num[pp] > 0) {
            ct++;
            num[pp] += num[px];
            pa[px] = pp;
        }
        num[px]--;
        prev = x;
    }

    //cout <<endl;
    

    cout << ct;
}

/*
7 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7

*/