题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3237
对询问序列进行分治，然后利用并查集进行缩点（修改边即可），这样时间复杂度就可以达到了O(k log k)。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )
const int maxn = 101000 , maxm = 201000 , maxk = 101000 , maxd = 19 ;
int father[ maxn ] ;
inline void Init_us( int V ) {
rep( i , V ) father[ i ] = 0 ;
}
inline int getfa( int now ) {
int i = now ; for ( ; father[ i ] ; i = father[ i ] ) ;
for ( int j = now , k ; father[ j ] ; k = father[ j ] , father[ j ] = i , j = k ) ;
return i ;
}
inline void merge( int s , int t ) {
int u = getfa( s ) , v = getfa( t ) ;
if ( u != v ) father[ u ] = v ;
}
int edge[ maxm ][ 2 ] , en[ maxk ] , e[ maxk ][ 4 ][ 3 ] , n , m , k , num[ maxn ] , temp[ maxd ][ maxk ][ 4 ][ 2 ] , trans[ maxn ] ;
bool used[ maxm ] , ans[ maxk ] ;
inline int transform( int V , int l , int r ) {
rep( i , V ) num[ i ] = 0 ;
int cnt = 0 , now ;
rep( i , V ) {
if ( ! num[ now = getfa( i ) ] ) num[ now ] = ++ cnt ;
trans[ i ] = num[ now ] ;
}
REP( i , l , r ) Rep( j , en[ i ] ) {
e[ i ][ j ][ 0 ] = trans[ e[ i ][ j ][ 0 ] ] , e[ i ][ j ][ 1 ] = trans[ e[ i ][ j ][ 1 ] ] ;
}
return cnt ;
}
inline void Save( int l , int r , int lev ) {
REP( i , l , r ) Rep( j , en[ i ] ) {
temp[ lev ][ i ][ j ][ 0 ] = e[ i ][ j ][ 0 ] , temp[ lev ][ i ][ j ][ 1 ] = e[ i ][ j ][ 1 ] ;
}
}
inline void Load( int l , int r , int lev ) {
REP( i , l , r ) Rep( j , en[ i ] ) {
e[ i ][ j ][ 0 ] = temp[ lev ][ i ][ j ][ 0 ] , e[ i ][ j ][ 1 ] = temp[ lev ][ i ][ j ][ 1 ] ;
}
}
int VI ;
inline void Init( ) {
scanf( "%d%d" , &n , &m ) ;
rep( i , m ) scanf( "%d%d" , edge[ i ] , edge[ i ] + 1 ) ;
scanf( "%d" , &k ) ;
memset( used , false , sizeof( used ) ) ;
rep( i , k ) {
scanf( "%d" , en + i ) ;
Rep( j , en[ i ] ) {
int x ; scanf( "%d" , &x ) ; used[ x ] = true ;
e[ i ][ j ][ 0 ] = edge[ x ][ 0 ] , e[ i ][ j ][ 1 ] = edge[ x ][ 1 ] , e[ i ][ j ][ 2 ] = x ;
}
}
Init_us( n ) ;
rep( i , m ) if ( ! used[ i ] ) merge( edge[ i ][ 0 ] , edge[ i ][ 1 ] ) ;
VI = transform( n , 1 , k ) ;
}
int flag[ maxm ] , tag = 0 ;
void solve( int V , int l , int r , int lev ) {
if ( l == r ) {
ans[ l ] = V == 1 ; return ;
}
int mid = ( l + r ) >> 1 ;
++ tag ;
REP( i , l , mid ) Rep( j , en[ i ] ) flag[ e[ i ][ j ][ 2 ] ] = tag ;
Init_us( V ) ;
REP( i , ( mid + 1 ) , r ) Rep( j , en[ i ] ) if ( flag[ e[ i ][ j ][ 2 ] ] < tag ) {
merge( e[ i ][ j ][ 0 ] , e[ i ][ j ][ 1 ] ) ;
}
Save( l , mid , lev ) ;
int v = transform( V , l , mid ) ;
solve( v , l , mid , lev + 1 ) ;
Load( l , mid , lev ) ;
++ tag ;
REP( i , ( mid + 1 ) , r ) Rep( j , en[ i ] ) flag[ e[ i ][ j ][ 2 ] ] = tag ;
Init_us( V ) ;
REP( i , l , mid ) Rep( j , en[ i ] ) if ( flag[ e[ i ][ j ][ 2 ] ] < tag ) {
merge( e[ i ][ j ][ 0 ] , e[ i ][ j ][ 1 ] ) ;
}
v = transform( V , mid + 1 , r ) ;
solve( v , mid + 1 , r , lev + 1 ) ;
}
int main( ) {
Init( ) ;
memset( flag , 0 , sizeof( flag ) ) ;
solve( VI , 1 , k , 0 ) ;
rep( i , k ) printf( ans[ i ] ? "Connected\n" : "Disconnected\n" ) ;
return 0 ;
}
网友评论