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; }