Untitled

 avatar
unknown
plain_text
a year ago
2.0 kB
4
Indexable
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define LD long double

const int N = 100010;

int inf = 1e9;
int mod = 1e9 + 7;

class wunionfind {
  public:
    int *id, *sz;
    int cnt = 0;
    wunionfind(int n = N) {
        id = new int[n + 1];
        sz = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            id[i] = i;
            sz[i] = 1;
        }
        cnt = n;
    }
    int root(int idx) {
        int x = idx;
        while(x != id[x]) {
            id[x] = id[id[x]];
            x = id[x];
        }
        return x;
    }
    bool uni(int a, int b) {
        int x = root(a), y = root(b);
        if(sz[x] < sz[y]) {
            swap(x, y);
        }
        if (x != y) {
            cnt--;
            id[y] = x;
            sz[x] += sz[y];
            sz[y] = 0;
            return false;
        }
        return true;
    }
};

signed main()
{
    //freopen("IN", "r", stdin);
    //freopen("OUT", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, q; cin >> n >> m >> q;

    bool marked[m + 1];
    memset(marked, false, sizeof(marked));

    pair<int,int> query[q];
    pair<int,int> edge[m + 1];

    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
    }

    for(int i = 0; i < q; i++) {
        int t; cin >> t;
        if(t == 2) query[i] = {2, -1};
        else {
            int x; cin >> x;
            query[i] = {1, x};
            marked[x] = true;
        }
    }

    wunionfind W(n);

    for(int i = 1; i <= m; i++) {
        if(!marked[i]) {
            int u = edge[i].first;
            int v = edge[i].second;
            W.uni(u, v);
        }
    }

    vector<int> ans;

    for(int i = q - 1; i >= 0; i--) {
        if(query[i].first == 2) ans.push_back(W.cnt);
        else {
            int u = query[i].second;
            W.uni(edge[u].first, edge[u].second);
        }
    }

    reverse(ans.begin(), ans.end());

    for(int u : ans) cout << u << "\n";

    return 0;
}
Editor is loading...
Leave a Comment