1076 2条不相交的路径

1 秒 131,072 KB 40 分 4 级题

给出一个无向图G的顶点V和边E。进行Q次查询，查询从G的某个顶点V[s]到另一个顶点V[t]，是否存在2条不相交的路径。（两条路径不经过相同的边）

（注，无向图中不存在重边，也就是说确定起点和终点，他们之间最多只有1条路）

 收起

输入

第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，中间用空格分隔，表示查询的起点和终点。

输出

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

输入样例

4 4 1 2 2 3 1 3 1 4 5 1 2 2 3 3 1 2 4 1 4

输出样例

Yes Yes Yes No No

题解：如果两点之间有两条不同的路径，那么这两个点之间肯定有环，那么就是 缩点 了。

#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<math.h> #include<vector> #include<bitset> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<algorithm> #define eps (1e-8) #define MAX 0x3f3f3f3f #define u_max 1844674407370955161 #define l_max 9223372036854775807 #define i_max 2147483647 #define re register #define nth(k,n) nth_element(a,a+k,a+n); // 将 第K大的放在k位 #define ko() for(int i=2;i<=n;i++) s=(s+k)%i // 约瑟夫 #define ok() v.erase(unique(v.begin(),v.end()),v.end()) // 排序,离散化 using namespace std; inline int read(){ char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' & c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } typedef long long ll; const double pi = atan(1.)*4.; const int M=1e3+5; const int N=5e4+5; int n,m; vector<int>vect[N]; int v[N],low[N]; int dfn[N],color[N],s[N],num[N]; int st=0,tim=0,col=0; void tarjan(int x,int fa){ s[++st]=x; v[x]=1; dfn[x]=tim; low[x]=tim++; for(int i=0;i<vect[x].size();i++){ int y=vect[x][i]; if(y==fa) continue; if(!v[y]) tarjan(y,x); if(v[y]==1) low[x]=min(low[x],low[y]); } if(dfn[x]==low[x]){ col++; while(true){ int t=s[st]; st--; v[t]=-1; color[t]=col; num[col]++; if(t==x) break; } } } int main(){ scanf("%d %d",&n,&m); int x,y,q; while(m--){ scanf("%d %d",&x,&y); vect[x].push_back(y); vect[y].push_back(x); } for(int i=1;i<=n;i++) if(!v[i]) tarjan(i,i); scanf("%d",&q); while(q--){ scanf("%d %d",&x,&y); if(color[x]==color[y]) printf("Yes\n"); else printf("No\n"); } return 0; }