本文主要是介绍51nod1076(边双联通分量)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题意：给出一个无向图G的顶点V和边E。进行Q次查询，查询从G的某个顶点V[s]到另一个顶点V[t]，是否存在2条不相交的路径。（两条路径不经过相同的边）
（注，无向图中不存在重边，也就是说确定起点和终点，他们之间最多只有1条路）
代码：
#include <queue>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int siz=50005;
struct node{int to,id;
};
vector<node> G[siz];
int low[siz],dfn[siz],sig[siz],vis[siz];
void dfs(int s,int fa,int id){int i,tmp;vis[s]=1;dfn[s]=low[s]=id++;for(i=0;i<G[s].size();i++){tmp=G[s][i].to;if(vis[tmp]==0){dfs(tmp,s,id);low[s]=min(low[s],low[tmp]);if(low[tmp]>dfn[s])sig[G[s][i].id]=1;}else if(tmp!=fa)low[s]=min(low[s],dfn[tmp]);}
}
void cal(int s,int id){int i,tmp;vis[s]=id;for(i=0;i<G[s].size();i++){tmp=G[s][i].to;if(vis[tmp]||sig[G[s][i].id])continue;cal(tmp,id);}
} //先跑出所有桥，再dfs标记一下，实现
int main(){ //边双联通分量int n,m,i,j,u,v,q,id;while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;i++)G[i].clear();for(i=1;i<=m;i++){scanf("%d%d",&u,&v);G[u].push_back((node){v,i});G[v].push_back((node){u,i});}memset(vis,0,sizeof(vis));memset(sig,0,sizeof(sig));id=1;for(i=1;i<=n;i++){ //注意一下初始图可能不连通if(vis[i]==0)dfs(i,-1,id);} id=1;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){if(vis[i]==0){cal(i,id);id++;}}scanf("%d",&q);while(q--){scanf("%d%d",&u,&v);if(vis[u]==vis[v])puts("Yes");elseputs("No");}}return 0;
}
这篇关于51nod1076(边双联通分量)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
