[原创]51nod 1076 2条不相交的路径 [双联通]【图论】

2017-06-09 20:47:42 Tabris_ 阅读数：358

博客爬取于2020-06-14 22:40:00
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72971158

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1076
———————————————————————————————————————————
1076 2条不相交的路径
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
给出一个无向图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。
Input示例
4 4
1 2
2 3
1 3
1 4
5
1 2
2 3
3 1
2 4
1 4
Output示例
Yes
Yes
Yes
No
No
———————————————————————————————————————————

题目问的是 两个点有没有两条不想交的路径,其实就是这两个节点在不在同一个双联通分量里面 如果在就是 否则不是

所以最后就是求双联通了,

双联通用tarjan即可,其实和强连通类似,

只不过对与low 要与所有的儿子进行比较,剩下的就和强连通一模一样了,其实就是一回事儿

附本题代码
———————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# include<bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 25000+7;
const int MOD = 1e9+7;
const int INF = (~(1<<31))>>1;

# define abs(x) ((x)>0?(x):-(x))

/****************************************************/

vector<int>G[N];

int dfn[N],low[N],vis[N],color[N],cnt,tot;
int mystack[N],len;

void tarjan(int u,int f){
    dfn[u]=low[u]=++cnt;
    vis[u]=1;mystack[++len]=u;
    int gz=G[u].size();
    for(int i=0,to;i<gz;i++){
        to=G[u][i];
        if(to==f) continue;
        if(vis[to]==0)tarjan(to,u);
        low[u]=min(low[u],low[to]);
    }
    if(low[u]==dfn[u]){
        ++tot;
        do{
            color[mystack[len]]=tot;
            vis[mystack[len]]=2;
        }while(mystack[len--]!=u);
    }
}
int n,m;
int main(){
    tot=cnt=len=0;
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for(int i=1;i<=n;i++) if(vis[i]==0) tarjan(i,0);
//    for(int i=1;i<=n;i++)printf("%d ",color[i]);puts("");
    int q,u,v;scanf("%d",&q);
    while(q--){
        scanf("%d%d",&u,&v);

        if(color[u]==color[v])
            puts("Yes");
        else puts("No");
    }
    return 0;
}