51nod 1076 2条不相交的路径【边连通分量】

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1076

题意：

给出一个无向图G的顶点V和边E。进行Q次查询，查询从G的某个顶点V[s]到另一个顶点V[t]，是否存在2条不相交的路径。（两条路径不经过相同的边） （注，无向图中不存在重边，也就是说确定起点和终点，他们之间最多只有1条路） Input

第1行：2个数M N，中间用空格分开，M是顶点的数量，N是边的数量。（2 <= M <= 25000, 1 <= N <= 50000) 第2 - N + 1行，每行2个数，中间用空格分隔，分别是N条边的起点和终点的编号。例如2 4表示起点为2，终点为4，由于是无向图，所以从4到2也是可行的路径。 第N + 2行，一个数Q，表示后面将进行Q次查询。(1 <= Q <= 50000) 第N + 3 - N + 2 + Q行，每行2个数s, t，中间用空格分隔，表示查询的起点和终点。

Output

共Q行，如果从s到t存在2条不相交的路径则输出Yes，否则输出No。

分析：

题意就是边连通分量的定义啊！ 求边连通分量的步骤： 先做一次dfs标记出所有的桥，然后再做一次dfs找出边双连通分量。 因为边双连通分量没有公共节点 ，所以只要在第二次dfs的时候保证不经过桥即可。

代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e4+7; struct node { int to,bridge; }; int low[N],pre[N],ecc[N],dfs_clock; vector<node>g[N]; void dfs(int u,int fa) { low[u]=pre[u]=++dfs_clock; for(int i=0;i<g[u].size();i++){ int v=g[u][i].to; if(!pre[v]){ dfs(v,u); low[u]=min(low[v],low[u]); if(pre[u]<low[v])g[u][i].bridge=1; } else if(fa!=v){ low[u]=min(low[u],pre[v]);; } } } void dfs2(int u,int fa,int id) { ecc[u]=id; for(int i=0;i<g[u].size();i++){ int v=g[u][i].to; if(ecc[v]||g[u][i].bridge)continue; dfs2(v,u,id); } } int n,m,u,v,Q; int main() { // freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); node t; for(int i=0;i<m;i++){ scanf("%d%d",&u,&v); t.to=v,t.bridge=0; g[u].push_back(t); t.to=u; g[v].push_back(t); } dfs_clock=0; memset(pre,0,sizeof(pre)); memset(ecc,0,sizeof(ecc)); for(int i=1;i<=n;i++){ if(!pre[i])dfs(i,-1); } for(int i=1;i<=n;i++){ if(!ecc[i])dfs2(i,-1,i); } scanf("%d",&Q); while(Q--){ scanf("%d%d",&u,&v); if(ecc[u]==ecc[v])puts("Yes"); else puts("No"); } return 0; }