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