博客

题目：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;
}