Codeforces 292D Connected Components (并查集)

题意 给出一张无向图，每次询问删去第Li--Ri 条边

求此时有多少个连通块

题解

求出一个前缀 Li 表示 加入前 i 条边时图的连通状况

以及一个后缀 Ri 表示 加入后 i 条边时图的连通状况

对于每个询问 删除 s--t 条边

只要将 L s-1 和 R t+1 合并 一下 就行了

合并 其实 就是讲 s-1 和 t+1 对应的 f[ i ] Union 一下就行了

为什么 这就相当于把前缀 i 和 后缀 i 通过一条边相连 ，两个就是连通的了

这样图就合并了

 

1 #include 
     
       2 using namespace std ; 3  4 const int N = 511,M = 10011 ;  5 struct bing{ 6     int i,e,f[N] ;  7     void init()  8     { 9         e = 0 ; 10         for(i=0;i
      
       =1;i--) 36         r[ i ] = r[ i+1 ] , r[ i ].Union( from[ i ],to[ i ] ) ; 37         38     scanf("%d",&Q) ; 39     while(Q--)40     {41         scanf("%d%d",&s,&t) ; 42         bing tmp = l[s-1] ; 43         for(int i=1;i<=n;i++) tmp.Union( l[ s-1 ].f[ i ],r[ t+1 ].f[ i ] ) ; 44         printf("%d\n",n-tmp.e) ;   45     }46     47     return 0 ; 48 }