luoguP5227 [AHOI2013]连通图

题意

虽然没用线段树，但是仍然是线段树分治的思想。

考虑分治询问序列，假设当前在\([l,r]\)，我们将\([1,l-1]\)和\([r+1,Q]\)的与\([l,r]\)内不重复的边都连上了。

先将\([mid+1,r]\)中与\([l,mid]\)不重复的边都连上，之后递归\([l,mid]\)，再将之前的操作撤销，将\([l,mid+1]\)中与\([mid+1,r]\)不重复的边都连上，之后递归\([mid+1,r]\)。

发现当低递归到\([l,l]\)时，整个并查集正好是第\(l\)组询问的图的状态。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=2*1e5+10;
const int maxQ=1e5+10;
int n,m,Q,top;
int fa[maxn],size[maxn];
bool ans[maxn],check[maxm];
struct Edge{int u,v;}E[maxm];
struct node{int x,y,sizey;}sta[maxQ];
vector<int>edge[maxQ];
inline int read()
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
int find(int x){return fa[x]==x?x:find(fa[x]);}
inline void merge(int u,int v,bool op)
{
    int x=find(u),y=find(v);
    if(x==y)return;
    if(size[x]>size[y])swap(x,y);
    if(op)sta[++top]=(node){x,y,size[y]};
    fa[x]=y;size[y]+=size[x];
}
inline void cut(int id)
{
    int x=sta[id].x,y=sta[id].y;
    fa[x]=x;size[y]=sta[id].sizey;
}
void solve(int l,int r)
{
    if(l==r){ans[l]=(size[find(1)]==n);return;}
    int now=top,mid=(l+r)>>1;
    for(int i=mid+1;i<=r;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            check[edge[i][j]]=1;
    for(int i=l;i<=mid;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            check[edge[i][j]]=0;
    for(int i=mid+1;i<=r;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            if(check[edge[i][j]])merge(E[edge[i][j]].u,E[edge[i][j]].v,1);
    solve(l,mid);
    while(top>now)cut(top),top--;
    for(int i=l;i<=mid;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            check[edge[i][j]]=1;
    for(int i=mid+1;i<=r;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            check[edge[i][j]]=0;
    for(int i=l;i<=mid;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            if(check[edge[i][j]])merge(E[edge[i][j]].u,E[edge[i][j]].v,1);
    solve(mid+1,r);
    while(top>now)cut(top),top--;
    for(int i=l;i<=mid;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            check[edge[i][j]]=0;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;
    for(int i=1;i<=m;i++)E[i].u=read(),E[i].v=read();
    Q=read();
    for(int i=1;i<=Q;i++)
    {
        int k=read(),id;
        while(k--)id=read(),edge[i].push_back(id);
    }
    for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;
    for(int i=1;i<=Q;i++)
        for(unsigned int j=0;j<edge[i].size();j++)
            check[edge[i][j]]=1;
    for(int i=1;i<=m;i++)if(!check[i])merge(E[i].u,E[i].v,0);
    solve(1,Q);
    for(int i=1;i<=Q;i++)puts(ans[i]?"Connected":"Disconnected");
    return 0;
}