Yuki 416 旅行会社 ( Union Find, Smaller to Larger, Time Reverse )
題意:
給一個圖,和破壞邊的順序 ( 不一定會將所有橋破壞 )。對於所有大於 0 的節點,求哪一次破壞後無法從 0 達到。若一開始就不能到達,輸出 0,若破壞完依然能到達,輸出 -1。
資料規模:
節點數 2≤N≤1e5
初始橋的數量 1≤M≤2e5
解法:
從破壞完的樣貌開始復原,每次用並查集,加上啟發式合併的技巧合併。合併時有個例外,在含 0 的集合和另一個集合合併時,必須將另一個集合裡的元素一一枚舉合併到 0 裡,且更新答案。
時間 / 空間複雜度:
O( N lg N ) / O( N )
int N, M, Q; vp bridge; vp destroy; void init(){ cin >> N >> M >> Q; bridge = vp( M ); for( int i = 0; i < M; ++i ) cin >> bridge[ i ].first >> bridge[ i ].second, --bridge[ i ].first, --bridge[ i ].second; destroy = vp( Q ); for( int i = 0; i < Q; ++i ) cin >> destroy[ i ].first >> destroy[ i ].second, --destroy[ i ].first, --destroy[ i ].second; } set< pii > destroyed; struct dsu{ vi fa; vvi member; dsu( int sz ){ fa = vi( sz ); member = vvi( sz ); for( int i = 0; i < sz; ++i ) fa[ i ] = i, member[ i ].emplace_back( i ); } int find( int x ){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); } int unite( int x, int y ){ int a = find( x ); int b = find( y ); if( a == b ) return 0; if( not ( member[ a ].size() >= member[ b ].size() ) ) swap( a, b ); for( int x : member[ b ] ) member[ a ].emplace_back( x ); member[ b ].clear(), member[ b ].shrink_to_fit(); fa[ b ] = a; return 1; } int unite( int x, int y, vi &ans, int id ){ int a = find( x ); int b = find( y ); if( a == b ) return 0; if( not ( member[ a ].size() >= member[ b ].size() ) ) swap( a, b ); if( b == find( 0 ) ) swap( a, b ); for( int x : member[ b ] ){ member[ a ].emplace_back( x ); if( a == find( 0 ) ) ans[ x ] = id; } member[ b ].clear(), member[ b ].shrink_to_fit(); fa[ b ] = a; return 1; } int connected( int x, int y ){ int a = find( x ); int b = find( y ); return a == b; } } *uf; vi ans; void preprocess(){ for( int i = 0; i < Q; ++i ) destroyed.emplace( destroy[ i ] ); uf = new dsu( N ); for( int i = 0; i < M; ++i ) if( not destroyed.count( bridge[ i ] ) ) uf->unite( bridge[ i ].first, bridge[ i ].second ), uf->unite( bridge[ i ].second, bridge[ i ].first ); ans = vi( N ); for( int i = 0; i < N; ++i ) if( uf->find( i ) == uf->find( 0 ) ) ans[ i ] = -1; for( int i = Q - 1; i >= 0; --i ) uf->unite( destroy[ i ].first, destroy[ i ].second, ans, i + 1 ); } void solve(){ for( int i = 1; i < N; ++i ) cout << ans[ i ] << endl; }