本文共 1773 字，大约阅读时间需要 5 分钟。
题意：
思路：
边双连通分量，跑一遍存储一下即可。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std; 13 typedef long long ll; 14 const int INF = 0x3f3f3f3f; 15 const int maxn=50000+5; 16 const int mod=1e9+7; 17 18 int n, m; 19 int tot; 20 int head[maxn]; 21 int ebbc[maxn],pre[maxn],eccno[maxn],low[maxn]; 22 int ebbc_cnt,dfs_clock; 23 24 stack S; 25 26 struct node 27 { 28 int v,next; 29 }e[2*maxn]; 30 31 void addEdge(int u, int v) 32 { 33 e[tot].v=v; 34 e[tot].next=head[u]; 35 head[u]=tot++; 36 } 37 38 int tarjan(int u, int fa) 39 { 40 int lowu=pre[u]=++dfs_clock; 41 S.push(u); 42 for(int i=head[u];i!=-1;i=e[i].next) 43 { 44 int v=e[i].v; 45 if(!pre[v]) 46 { 47 int lowv=tarjan(v,u); 48 lowu=min(lowu,lowv); 49 } 50 else if(v!=fa) 51 lowu=min(lowu,pre[v]); 52 } 53 if(pre[u]==lowu) 54 { 55 ebbc_cnt++; 56 for(;;) 57 { 58 int tmp=S.top(); S.pop(); 59 eccno[tmp]=ebbc_cnt; 60 if(tmp==u) break; 61 } 62 } 63 return low[u]=lowu; 64 } 65 66 void find_ebbc() 67 { 68 ebbc_cnt=dfs_clock=0; 69 memset(pre,0,sizeof(pre)); 70 for(int i=1;i<=n;i++) 71 { 72 if(!pre[i]) tarjan(i,-1); 73 } 74 } 75 76 int main() 77 { 78 //freopen("in.txt","r",stdin); 79 while(~scanf("%d%d",&n,&m)) 80 { 81 tot=0; 82 memset(head,-1,sizeof(head)); 83 for(int i=1;i<=m;i++) 84 { 85 int u,v; 86 scanf("%d%d",&u,&v); 87 addEdge(u,v); 88 addEdge(v,u); 89 } 90 find_ebbc(); 91 int q; 92 scanf("%d",&q); 93 while(q--) 94 { 95 int u,v; 96 scanf("%d%d",&u,&v); 97 if(eccno[u]==eccno[v]) puts("Yes"); 98 else puts("No"); 99 }100 }101 return 0;102 }
转载于:https://www.cnblogs.com/zyb993963526/p/7400238.html
