BZOJ3237:[AHOI2013]连通图(线段树分治,并查集)

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

Solution

线段树分治，根据询问把每条边存在的时间区间拆成几个区间，然后覆盖到线段树上，最后$DFS$一遍线段树。用带撤销的并查集维护一下连通块个数，到线段树叶子节点的时候根据连通块个数输出答案。

常数有点大……离$TLE$只有$0.3s$……在被卡的边缘疯狂试探……

Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #define N (100009)
 5 using namespace std;
 6 
 7 int n,cnt,m,q,top,u[N<<1],v[N<<1];
 8 int fa[N],dep[N];
 9 pair<int,int>stack[N];
10 vector<int>p[N<<1],Segt[N<<2];
11 
12 char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
13 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
14 
15 inline int read()
16 {
17     int x=0,w=1; char c=getchar();
18     while (c<'0' || c>'9') {if (c=='-') w=-1; c=getchar();}
19     while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();
20     return x*w;
21 }
22 
23 void Update(int now,int l,int r,int l1,int r1,int k)
24 {
25     if (l>r1 || r<l1) return;
26     if (l1<=l && r<=r1) {Segt[now].push_back(k); return;}
27     int mid=(l+r)>>1;
28     Update(now<<1,l,mid,l1,r1,k); Update(now<<1|1,mid+1,r,l1,r1,k);
29 }
30 
31 int Find(int x)
32 {
33     return x==fa[x]?x:Find(fa[x]);
34 }
35 
36 void DFS(int now,int l,int r)
37 {
38     int mid=(l+r)>>1,tmp=top;
39     for (int i=0; i<Segt[now].size(); ++i)
40     {
41         int x=u[Segt[now][i]],y=v[Segt[now][i]];
42         int fx=Find(x),fy=Find(y);
43         if (fx==fy) continue;
44         if (dep[fx]>dep[fy]) swap(fx,fy);
45         fa[fx]=fy; dep[fy]+=(dep[fx]==dep[fy]); cnt--;
46         stack[++top]=make_pair(fx,fy);
47     }
48     if (l<r) DFS(now<<1,l,mid), DFS(now<<1|1,mid+1,r);
49     else puts(cnt==1?"Connected":"Disconnected");
50     for (int i=top; i>tmp; --i)
51     {
52         int fx=stack[i].first,fy=stack[i].second;
53         fa[fx]=fx; dep[fy]-=(dep[fx]==dep[fy]); cnt++;
54     }
55     top=tmp;
56 }
57 
58 int main()
59 {
60     n=cnt=read(); m=read();
61     for (int i=1; i<=n; ++i) fa[i]=i, dep[i]=1;
62     for (int i=1; i<=m; ++i) u[i]=read(), v[i]=read();
63     q=read();
64     for (int i=1; i<=q; ++i)
65     {
66         int c=read();
67         for (int j=1; j<=c; ++j) p[read()].push_back(i);
68     }
69     for (int i=1; i<=m; ++i)
70     {
71         p[i].push_back(q+1);
72         int last=1;
73         for (int j=0; j<p[i].size(); ++j)
74             Update(1,1,q,last,p[i][j]-1,i), last=p[i][j]+1;
75     }
76     DFS(1,1,q);
77 }