SMMR-T155: London Bridge

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

#define pii pair<int, int>

stack<pii> edges;
vector<int> DSet;
vector<int> ranks;
int nv, ne;

int DSFind(int x){
    if(DSet[x] == x){
        return x;
    } else {
        return DSet[x] = DSFind(DSet[x]);
    }
}

void DSUnion(int x, int y){
    int hx = DSFind(x);
    int hy = DSFind(y);
    if(ranks[hx] > ranks[hy]){
        DSet[hy] = hx;
    } else {
        DSet[hx] = hy;
        if(ranks[hx] == ranks[hy]){
            ++ranks[hy];
        }
    }
    return;
}

int main(){

    int u, v, need;

    scanf("%d %d", &nv, &ne);
    DSet.assign(nv + 1, 0);
    ranks.assign(nv + 1, 1);
    for(int i = 1; i <= nv; ++i){
        DSet[i] = i;
    }

    for(int i = 1; i <= ne; ++i){
        scanf("%d %d", &u, &v);
        edges.push({u, v});
    }

    need = 0;
    for(int i = 1; i <= ne && !edges.empty(); ++i){
        int u = edges.top().first;
        int v = edges.top().second;
        edges.pop();
        if(DSFind(u) != DSFind(v)){
            DSUnion(u, v);
            need = i;
        }
    }

    cout << ne - need;

    return 0;
}