连通图
Time Limit: 20 Sec Memory Limit: 512 MB[][][]Description
Input
Output
Sample Input
4 5 1 2 2 3 3 4 4 1 2 4 3 1 5 2 2 3 2 1 2
Sample Output
Connected Disconnected Connected
HINT
N<=100000 M<=200000 K<=100000
Main idea
给定一张无向联通图，询问删除掉若干条边后图是否联通，多次询问。
Solution
首先我们看到删边判联通，第一反应想到了LCT，由于图不是一棵树，无法用LCT实现，那么我们否决掉了动态维护的方法。
根据可以离线询问这一特征来思考如何操作，发现k(询问数)<=100000，显然是log级别的做法，结合可离线的特征，这时候只剩下了对于所有询问一起进行操作的方法 ，现在我们得出了算法：CDQ分治。 发现直接删边操作较为困难，我们逆向思维，考虑如何在一个空的图上加边。 先考虑只有两个询问的情况，假定我们的询问删边集合为A,B，那么显然想到了先把不在A中并且不在B中边加入（这时称其为状态一），然后分开处理，先加入不在A中但是在B中的边，判下是否联通就得到了A中的答案，然后回到状态一，加入不在B中在A中的边，判断一下得到了B的答案。 然后基于这样的整个思路，我们考虑如何将两个集合拓展到多个集合。 立马想到了分治，对于所有集合分治使其类同于A,B两种“大集合”，然后继续分治，最后必然可以归于仅有两个小集合的情况，然后向上回溯即可。加边用并查集加入即可。 我们来整理一下CDQ分治的思路： 1、加入不在左区间但在右区间的边； 2、对于左区间继续分治； 3、回到上一层的状态（在分治的时候记录并查集中改变了的父子关系，暴力修改回去即可） 4、加入不在右区间但在左区间的边； 5、对于右区间继续分治； …… 最后判断是否联通的时候又发现一开始的整张图是处于连通状态的，所以我们只要判断删掉的边的端点是否连通即可。Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 const int ONE=200005; 11 12 int n,m,Bian; 13 int fat[ONE],cnt; 14 int PD[ONE]; 15 int Ans[ONE]; 16 17 struct power 18 { 19 int x,y; 20 }a[ONE*2],q[ONE*100]; 21 22 struct point 23 { 24 int c; 25 int b[5]; 26 }quey[ONE]; 27 28 int get() 29 { 30 int res,Q=1; char c; 31 while( (c=getchar())<48 || c>57) 32 if(c=='-')Q=-1; 33 if(Q) res=c-48; 34 while((c=getchar())>=48 && c<=57) 35 res=res*10+c-48; 36 return res*Q; 37 } 38 39 int Find(int x) 40 { 41 if(x!=fat[x]) 42 { 43 q[++cnt].x=x; q[cnt].y=fat[x]; 44 fat[x]=Find(fat[x]); 45 } 46 return fat[x]; 47 } 48 49 void Un(int x,int y) 50 { 51 int f1=Find(x); 52 int f2=Find(y); 53 if(f1!=f2) 54 { 55 q[++cnt].x=f2; q[cnt].y=fat[f2]; 56 fat[f2]=f1; 57 } 58 } 59 60 int Get_pd(int l) 61 { 62 int pd=1; 63 for(int i=1;i<=quey[l].c;i++) 64 { 65 int j=quey[l].b[i]; 66 if(Find(a[j].x) != Find(a[j].y)) 67 { 68 pd=0; 69 break; 70 } 71 } 72 return pd; 73 } 74 75 void Mark(int l,int r,int t) 76 { 77 for(int i=l;i<=r;i++) 78 { 79 for(int j=1;j<=quey[i].c;j++) 80 PD[quey[i].b[j]]=t; 81 } 82 } 83 84 void Add(int l,int r) 85 { 86 for(int i=l;i<=r;i++) 87 { 88 for(int j=1;j<=quey[i].c;j++) 89 { 90 int num=quey[i].b[j]; 91 if(PD[num]) continue; 92 Un(a[num].x,a[num].y); 93 } 94 } 95 } 96 97 void Back(int Now_cnt) 98 { 99 for(;cnt>Now_cnt;cnt--) 100 fat[q[cnt].x]=q[cnt].y;101 }102 103 void CDQ(int l,int r)104 {105 if(l==r)106 {107 Ans[l]=Get_pd(l);108 return;109 }110 111 int Now_cnt=cnt;112 int mid=(l+r)/2;113 Mark(l,mid,1); Add(mid+1,r); Mark(l,mid,0);114 CDQ(l,mid);115 116 Back(Now_cnt);117 Mark(mid+1,r,1); Add(l,mid); Mark(mid+1,r,0);118 CDQ(mid+1,r);119 }120 121 122 int main()123 {124 n=get(); Bian=get();125 for(int i=1;i<=n;i++) fat[i]=i;126 for(int i=1;i<=Bian;i++)127 {128 a[i].x=get(); a[i].y=get();129 }130 131 m=get();132 for(int i=1;i<=m;i++)133 {134 quey[i].c=get();135 for(int j=1;j<=quey[i].c;j++)136 quey[i].b[j]=get();137 }138 139 Mark(1,m,1);140 for(int i=1;i<=Bian;i++)141 {142 if(PD[i]) continue;143 Un(a[i].x,a[i].y);144 }145 Mark(1,m,0); cnt=0;146 147 CDQ(1,m);148 149 for(int i=1;i<=m;i++)150 {151 if(Ans[i]) printf("Connected");152 else printf("Disconnected");153 printf("\n");154 }155 }