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
     
       2 #include
      
        3 #include
       
         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
        
         stack[N];10 vector
         
          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
          
           >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
           
            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
            
             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