0w1

TimOJ 1671 Anansi's Cobweb ( Union Find + Time Reverse )

1671. Anansi's Cobweb @ Timus Online Judge
If we simulate it from the back instead, thinking the original edge destroying operation as adding, it will be possible to solve using elementary union find.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXQ = MAXM;

int n, m;
int q;
int del[ MAXQ ];
bool willDel[ MAXM ];

struct Edge{
    int u, v;
    Edge(int _u = -1, int _v = -1): u(_u), v(_v){}
} es[ MAXM ];

int ans[ MAXQ ];

struct UnionFind{
    int fa[ MAXN ];
    void init(){
        for(int i = 1; i <= n; ++i)
            fa[ i ] = i;
    }
    int find(int x){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); }
    bool unite(int x, int y){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b; return true;
    }
} uf;

void solve(){
    uf.init();
    int cnt = n;
    for(int i = 0; i < m; ++i) if( !willDel[ i ] )
        if( uf.unite( es[ i ].u, es[ i ].v ) )
            --cnt;
    for(int i = q - 1; i >= 0; --i){
        ans[ i ] = cnt;
        if( uf.unite( es[ del[ i ] ].u, es[ del[ i ] ].v ) )
            --cnt;
    }
    for(int i = 0; i < q; ++i)
        printf("%d%c", ans[ i ], i == q - 1 ? '\n' : ' ');
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
        scanf("%d%d", &es[ i ].u, &es[ i ].v);
    scanf("%d", &q);
    for(int i = 0; i < q; ++i){
        scanf("%d", &del[ i ]);
        willDel[ --del[ i ] ] = true;
    }
    solve();
    return 0;
}