51nod 1076 2条不相交的路径

给出一个无向图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 题意：给出一个无向图G的顶点V和边E。进行Q次查询，查询从G的某个顶点V[s]到另一个顶点V[t]，是否存在2条不相交的路径。（两条路径不经过相同的边） 思路：边双联通分量模板题 AC代码：

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int SIZE=100010; int head[SIZE],ver[SIZE*2],Next[SIZE*2]; int dfn[100010],low[SIZE],n,m,tot,num=0; bool bridge[SIZE*2]; void add(int x,int y) { ver[++tot]=y; Next[tot]=head[x]; head[x]=tot; } void tarjan(int x,int in_edge) { dfn[x]=low[x]=++num; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(!dfn[y]) { tarjan(y,i); low[x]=min(low[x],low[y]);//x，y是搜索树上的边 if(low[y]>dfn[x]) { bridge[i]=bridge[i^1]=true;//无向边看为双向边，i与i^1是一条边 } } else { if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);//x，y不是搜索树上的边 } } } int c[SIZE]; void dfs(int x,int dcc) { c[x]=dcc; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(c[y]||bridge[i])continue; dfs(y,dcc); } } int main() { cin>>n>>m; tot=1; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0); for(int i=1;i<=n;i++) if(!c[i]) { dfs(i,i); } int w; cin>>w; while(w--) { int p,q; cin>>p>>q; if(c[p]!=c[q]) cout<<"No"<<endl; else cout<<"Yes"<<endl; } }

这道题过的很迷，本来挺简单的，就是过不了，改了两天也过不了，后来没法了比着从打了一遍就过了。。。。真心无语。。。 错误代码：

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int SIZE=100010; int head[SIZE],ver[SIZE*2],Next[SIZE*2]; int dfn[SIZE],low[SIZE],n,m,tot,num; bool bridge[SIZE*2]; void add(int x,int y) { ver[++tot]=y; Next[tot]=head[x]; head[x]=tot; } void targan(int x,int in_edge) { dfn[x]=low[x]=++num; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(!dfn[y]) { targan(y,i); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]) { bridge[i]=bridge[i^1]=true; } } else { if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]); } } } int c[SIZE]; void dfs(int x,int dcc) { c[x]=dcc; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(c[y]||bridge[i])continue; dfs(y,dcc); } } int main() { int m,n; cin>>m>>n; for(int i=0;i<n;i++) { int x,y; cin>>x>>y; add(x,y); add(y,x); } for(int i=1;i<=m;i++) if(!dfn[i])targan(i,0); for(int i=1;i<=n;i++) if(!c[i]) { dfs(i,i); } for(int i=1;i<=m;i++) { cout<<i<<":"<<c[i]<<endl; } int w; cin>>w; while(w--) { int p,q; cin>>p>>q; if(c[p]!=c[q]) cout<<"No"<<endl; else cout<<"Yes"<<endl; } }