【Codeforces 639F】Bear and Chemistry | Mrsrz's blog

边双缩点，虚树。

题目大意：

给定一张无向图，每次询问给出 $n’$ 个点和 $m’$ 条额外边，要求回答在加入 $m’$ 条额外边后，这 $n’$ 个点两两之间是否存在两条不包含重复边的路径。询问独立，强制在线。

题解：

相当于每次询问加入若干条边后，这个点集是否在同一个边双里。

首先对原图进行缩点，得到一棵树。

然后每次把给定的点集以及额外边的端点建出来，并连上边。

在这张图上再跑边双，判断给定的点是否在同一个边双里即可。

时间复杂度 $O((n+m)\log n)$。

由于需要进行很多次求边双，可以把求边双的东西封装起来减少代码长度。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=3e5+6;
struct edge{
    int to,nxt;
}e[N<<2];
int n,m,head[N],dfn[N],cnt,bel[N],nodes,dep[N],fa[N],top[N],son[N],sz[N],idx,idfn[N],out[N],k,rt[N],rr;
vector<int>sta;
int U[N],V[N],a[N];
bool vis[N];
inline void addedge(int u,int v){
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
struct Graph{
    edge e[N<<2];
    int head[N],cnt,id[N],n,dfn[N],low[N],idx,sta[N],top,bel[N],vis[N],SCC;
    inline void addedge(int u,int v){
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    void clear(){
        for(int i=1;i<=n;++i)head[id[i]]=dfn[id[i]]=low[id[i]]=bel[id[i]]=0;
        n=idx=0,cnt=1;
    }
    void dfs(int now,int ie){
        dfn[now]=low[now]=++idx;
        vis[now]=1;
        sta[++top]=now;
        for(int i=head[now];i;i=e[i].nxt)
        if(i!=ie){
            const int v=e[i].to;
            if(!dfn[v]){
                dfs(v,i^1);
                low[now]=min(low[now],low[v]);
            }else if(vis[v])low[now]=min(low[now],dfn[v]);
        }
        if(dfn[now]==low[now]){
            ++SCC;
            int v;
            do{
                v=sta[top--];
                vis[v]=0;
                bel[v]=SCC;
            }while(v!=now);
        }
    }
    void init(){
        for(int i=1;i<=n;++i)
        if(!dfn[id[i]])dfs(id[i],0);
    }
    void ready(const vector<int>&sta){
        n=sta.size();
        for(int i=1;i<=n;++i)id[i]=sta[i-1];
    }
    void save_out(){
        for(int i=1;i<=n;++i)
        ::head[id[i]]=0,::bel[id[i]]=bel[id[i]];
        for(int i=1;i<=n;++i)
        for(int j=head[id[i]];j;j=e[j].nxt)
        if(bel[id[i]]!=bel[e[j].to])::addedge(bel[id[i]],bel[e[j].to]);
        ::nodes=SCC;
    }
    bool judge(int*a,int siz){
        const int&t=bel[a[1]];
        for(int i=2;i<=siz;++i)
        if(bel[a[i]]!=t)return 0;
        return 1;
    }
}G,H;
inline bool cmp(const int&a,const int&b){
    return dfn[a]<dfn[b];
}
void dfs(int now){
    rt[now]=rr;
    sz[now]=1,son[now]=0,vis[now]=1;
    for(int i=head[now];i;i=e[i].nxt)
    if(!vis[e[i].to]){
        dep[e[i].to]=dep[now]+1,fa[e[i].to]=now;
        dfs(e[i].to);
        sz[now]+=sz[e[i].to];
        if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
    }
}
void dfs2(int now){
    vis[now]=1;
    idfn[dfn[now]=++idx]=now;
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int i=head[now];i;i=e[i].nxt)
    if(!vis[e[i].to])dfs2(top[e[i].to]=e[i].to);
    out[now]=idx;
}
inline int LCA(int x,int y){
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
void build(){
    static int stk[N];
    int top=1;stk[1]=sta[0];
    for(int i=1;i<sta.size();++i){
        const int&v=sta[i];
        while(top&&out[stk[top]]<dfn[v])--top;
        if(top)H.addedge(stk[top],v);
        stk[++top]=v;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    G.clear();
    for(int i=1;i<=n;++i)G.id[i]=i;
    G.n=n;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        G.addedge(u,v);
    }
    G.init();
    G.save_out();
    memset(vis,0,sizeof vis);
    for(int i=1;i<=nodes;++i)if(!dep[i])dep[rr=i]=1,dfs(i);
    memset(vis,0,sizeof vis);
    for(int i=1;i<=nodes;++i)if(dep[i]==1)top[i]=1,dfs2(i);
    long long dat=0;
    for(int T=1;T<=k;++T){
        int nn,mm;
        cin>>nn>>mm;
        sta.clear();
        for(int i=1;i<=nn;++i){
            int x;
            cin>>x;
            x=(x+dat)%n;
            if(!x)x=n;
            sta.push_back(a[i]=bel[x]);
        }
        for(int i=1;i<=mm;++i){
            int x;
            cin>>x;
            x=(x+dat)%n;
            if(!x)x=n;
            sta.push_back(U[i]=bel[x]);
            cin>>x;
            x=(x+dat)%n;
            if(!x)x=n;
            sta.push_back(V[i]=bel[x]);
        }
        sort(sta.begin(),sta.end(),cmp);
        sta.erase(unique(sta.begin(),sta.end()),sta.end());
        for(int i=(int)sta.size()-1;i;--i)
        if(rt[sta[i]]==rt[sta[i-1]])
        sta.push_back(LCA(sta[i],sta[i-1]));
        sort(sta.begin(),sta.end(),cmp);
        sta.erase(unique(sta.begin(),sta.end()),sta.end());
        H.clear();
        H.ready(sta);
        build();
        for(int i=1;i<=mm;++i)H.addedge(U[i],V[i]);
        H.init();
        bool res=H.judge(a,nn);
        dat+=T*res;
        cout<<(res?"YES":"NO")<<'\n';
    }
    return 0;
}