51NOD 1076 2条不相交的路径 【点双连通分量】

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 相关问题 3条不相交的路径 1280 李陶冶 (题目提供者)

---

画画图就不难发现 满足条件的s和t必然在一个环中 求点双连通分量 判断s，t判断是否属于同一分量即可

---

#include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> #include<queue> #include<sstream> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> const int N=25000+5; const int M=50000+5; struct Edge { int to,next; }edge[2*M]; int head[N]; inline void addEdge(int k,int u,int v){ edge[k].to=v; edge[k].next=head[u]; head[u]=k; } int low[N],dfn[N]; int sta[N],top; int belong[N];//记录点i属于哪个联通块 //vector<vector<int> >ans;//ans[i][j]为第i个联通块的点 void tarjanBfs(int cur,int&sig,int&tcc,int from){ sta[++top]=cur; low[cur]=dfn[cur]=++sig; for(int i=head[cur];i!=-1;i=edge[i].next){ int to = edge[i].to; if(to==from){ continue; } if(!dfn[to]){//未遍历过 tarjanBfs(to,sig,tcc,cur); low[cur]=min(low[cur],low[to]); if(dfn[cur]<=low[to]){//疑似发现联通块 int cow = 1; int tmpTop=top; do{ ++cow; }while(sta[tmpTop--]!=to); if(cow>2){//超过2个点 belong[cur]=tcc; /* ans.push_back(vector<int>()); ans.back().push_back(cur); */ do{ belong[sta[top]]=tcc; //ans.back().push_back(sta[top]); }while(sta[top--]!=to); ++tcc; } else{ top=tmpTop; } } } else{ low[cur]=min(low[cur],low[to]); } } } int tarjan(int n){ int tcc=0,sig=0; //ans.clear(); fill(low,low+n+1,0); fill(dfn,dfn+n+1,0); fill(belong,belong+n+1,-1); top = -1; for(int i=1;i<=n;++i){ if(dfn[i]==0){ tarjanBfs(i,sig,tcc,-1); } } return tcc;//联通块个数 } int main() { //freopen("/home/lu/Documents/r.txt","r",stdin); //freopen("/home/lu/Documents/w.txt","w",stdout); int n,m,u,v; scanf("%d%d",&n,&m); fill(head,head+n+1,-1); for(int i =0;i<m;++i){ scanf("%d%d",&u,&v); addEdge(2*i,u,v); addEdge(2*i+1,v,u); } tarjan(n); int q; scanf("%d",&q); while(q--){ scanf("%d%d",&u,&v); puts((belong[u]==belong[v]&&belong[u]!=-1)?"Yes":"No"); } return 0; }