zoj4097

题意：
给你一幅图(vert<1e5,edge<2e5)，多组询问(<1e5)，每次询问有三个点,w,u,v 问你是否存在从w到u和v的边不相交路径。

边双联通缩点，特判图的连通性。

#include<bits/stdc++.h>
using namespace std;

struct Graph{
    static const int maxn=1e5+5, maxm=3e5+5;
    struct star{int v,nex;}edge[maxm<<1];
    int head[maxn],cnt;
    void ini(int n){
        for(int i=0;i<=n;i++) head[i]=-1;
        cnt=-1;
    }
    void add_edge(int u,int v){
        edge[++cnt]=star{v,head[u]};
        head[u]=cnt;
        edge[++cnt]=star{u,head[v]};
        head[v]=cnt;
    }
};

struct Tarjan:Graph{//双联通分量, 割边, 桥, 边双联通缩点
    struct Bridge{int u,v;}bridge[maxn];
    int dfn[maxn],low[maxn],belong[maxn],vis[maxn],sta[maxn],sta_,nums,bridge_;
    void ini(int n){
        for(int i=0;i<=n;i++) vis[i]=0;
        bridge_=0;
        nums=0;
        Graph::ini(n);
    }
    void tarjan(int u,int father,int&step){
        low[u]=dfn[u]=++step;
        sta[++sta_]=u;
        vis[u]=1;
        bool firsttimes=true;//用于判重边
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v==father&&firsttimes) {
                firsttimes=false;
                continue;
            }//父边
            if(vis[v]==1) low[u]=min(low[u],dfn[v]);//回边,终点在栈中
            else {//树边
                tarjan(v,u,step);
                low[u]=min(low[u],low[v]);
                if(low[v]>dfn[u]) bridge[++bridge_]=Bridge{u,v};
            }
        }
        if(low[u]==dfn[u]){
            while(sta[sta_]!=u) belong[sta[sta_--]]=nums+1;
            belong[sta[sta_--]]=++nums;
        }
    }
}graph;

struct Lca:Graph{// 不要忘记ini
    int dep[maxn],dad[maxn],siz[maxn],son[maxn],chain[maxn],dfn[maxn];
    void dfs1(int u,int father){//dfs1(1,0)
        dep[u]=dep[father]+1;//ini
        dad[u]=father;
        siz[u]=1;
        son[u]=-1;
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v==father)continue;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v;
        }
    }
    void dfs2(int u,int s,int&step){
        dfn[u]=++step;
        chain[u]=s;
        if(son[u]!=-1) dfs2(son[u],s,step);
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v!=son[u]&&v!=dad[u]) dfs2(v,v,step);
        }
    }
    int lca(int x,int y){
        while(chain[x]!=chain[y]){
            if(dep[chain[x]]<dep[chain[y]]) swap(x,y);//dep[chain[x]]>dep[chain[y]]
            x=dad[chain[x]];
        }
        return dep[x]<dep[y]?x:y;
    }
}tree;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

//Disjoint Set Union
struct Dsu{
    static const int maxn=1e5+5;
    int f[maxn];
    void ini(int n){for(int i=0;i<=n;i++)f[i]=i;}
    int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
    void join(int x,int y){f[find(x)]=find(y);}
}dsu,dsu2;

int main(){
    int T=read();
    while(T--){
        int n=read(),m=read(),q=read();
        graph.ini(n+1);
        dsu.ini(n+1);
        dsu2.ini(n+1);
        for(int i=0;i<m;i++) {
            int u=read(),v=read();
            graph.add_edge(u,v);
            dsu.join(u,v);
            dsu2.join(u,v);
        }
        for(int i=1;i<=n;i++){
            if(dsu2.find(i)!=dsu2.find(n+1)){
                dsu2.join(i,n+1);
                graph.add_edge(i,n+1);
            }
        }
        int step=0;
        graph.tarjan(n+1,0,step);
        tree.ini(graph.nums);
        for(int i=1;i<=graph.bridge_;i++){
            int u=graph.bridge[i].u,v=graph.bridge[i].v;
            tree.add_edge(graph.belong[u],graph.belong[v]);
        }
        tree.dfs1(graph.belong[n+1],0);
        step=0;
        tree.dfs2(graph.belong[n+1],graph.belong[n+1],step);
        for(int i=0;i<q;i++) {
            int w=read(),u=read(),v=read();
            int bw=graph.belong[w];
            int bu=graph.belong[u];
            int bv=graph.belong[v];
            int lcawu=tree.lca(bw,bu);
            int lcawv=tree.lca(bw,bv);
            int lcauv=tree.lca(bu,bv);
            int lcauw=lcawu,lcavw=lcawv,lcavu=lcauv;
            if(dsu.find(w)==dsu.find(u)&&dsu.find(w)==dsu.find(v)){
                if(bw==bu&&bw==bv) puts("Yes");//1
                else if(bu==bv&&bw!=bu) puts("No");//2
                else if(bu==bw&&bu!=bv) puts("Yes");//2
                else if(bv==bw&&bu!=bv) puts("Yes");//2
                else{//3
                    if(lcavw==bw&&lcawu==bu) puts("Yes");
                    else if(lcauw==bw&&lcawv==bv) puts("Yes");
                    else if(lcauw==bw&&tree.dep[lcauv]<=tree.dep[lcawv]) puts("Yes");
                    else if(lcavw==bw&&tree.dep[lcauv]<=tree.dep[lcawu]) puts("Yes");
                    else puts("No");
                }
            }
            else{
                puts("No");
            }
        }
    }
}




/*

1
5 4 1
4 3
1 2
1 4
5 3
1 5 2



*/