首页 > 代码库 > 51nod1076 (边双连通)

51nod1076 (边双连通)

题目大意:给定一个无向图,有N个节点(N<=25000)、M条边(M <=50000),没有重边。给Q(Q<=50000)个询问,每次询问输入两个节点,问是否存在两条从一个节点到另一个节点互不相交(不经过同一条边)的路径。

分析:

  边双连通图:如果一个无向连通图中去掉任意一条边,不改变图的连通性,或者说,对图中任意两个点,都存在两条互不相交的路径,都则称为边双连通图。

  题目即求询问的两个点是否在同一个边双连通分量中。用Tarjan算法。

  Tarjan算法大致原理就是从一个节点开始做dfs,用两个数组dfn和low记录结点被搜到的时间和结点所在边双连通分量的最小根结点。将正在搜索的结点入栈,如果搜到某个点u时,u的祖先v在栈内,且存在一条还未走过的边(u,v),则说明u,v属于同一个边双连通分量,low[u]=min(low[x],dfn[to]).若u的孩子还未访问过,则继续访问,并更新low[u]=min(low[u],low[v]).如果low[v]>dfn[u],说明v的孩子不能到达u的祖先,则边(u,v)是一条桥.去掉图中所有的桥后,连通分量即为边双连通分量.每个结点和每条边最多只访问一次,故复杂度为O(N+M).

 1 #include<iostream>
 2 #include<stack>
 3 #include<vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 using namespace std;
 7 const int N=25005,M=50005;
 8 int n,m,Q,s[M],t[M],p[N],start,aim,Instack[N],dfn[N],low[N],have[M],had[N],cnt=0,Delete[M];
 9 vector<int> G[N];
10 stack<int> sta;
11 int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
12 void dfs(int x){
13     had[x]=1;
14     low[x]=dfn[x]=cnt++;
15     Instack[x]=1;
16     for(int i=0;i<G[x].size();i++){
17         int e=G[x][i];
18         int to=s[e]==x?t[e]:s[e];
19         if(have[e])continue;
20         if(!had[to]){
21             have[e]=1;
22             dfs(to);
23             have[e]=0;
24             low[x]=min(low[x],low[to]);
25         }else if(Instack[to]&&!have[e]){
26             low[x]=min(low[x],dfn[to]);
27         }
28         if(low[to]>dfn[x])Delete[e]=1;
29     }
30     Instack[x]=0;
31 }
32 void Tarjan(int x){
33     if(had[x])return;
34     memset(Instack,0,sizeof(Instack));
35     memset(have,0,sizeof(have));
36     while(!sta.empty())sta.pop();
37     dfs(x);
38 }
39 int main(){
40 //    freopen("e:\\in.txt","r",stdin);
41 //    freopen("e:\\out.txt","w",stdout);
42     cin>>n>>m;
43     int a,b;
44     memset(had,0,sizeof(had));
45     memset(Delete,0,sizeof(Delete));
46     for(int i=0;i<m;i++){
47         cin>>a>>b;
48         G[--a].push_back(i);
49         G[--b].push_back(i);
50         s[i]=a;t[i]=b;
51     }
52     for(int i=0;i<n;i++)
53         Tarjan(i);
54     for(int i=0;i<n;i++)p[i]=i;
55     for(int i=0;i<m;i++){
56         if(Delete[i])continue;
57         int x=Find(s[i]),y=Find(t[i]);
58         if(x!=y)p[x]=y;
59     }
60     cin>>Q;
61     while(Q--){
62         cin>>start>>aim;
63         if(Find(--start)==Find(--aim))cout<<"Yes\n";
64         else cout<<"No\n";
65     }
66     return 0;
67 }

 

51nod1076 (边双连通)