基准时间限制: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
#include <cstdio> #define N 50050 int m,n,q,top,tim,cnt=1,sumcol,col[N],stack[N],low[N],dfn[N],head[N],nextt[N<<1],to[N<<1]; inline int min(int a,int b) {return a>b?b:a;} void tarjan(int x,int pre) { low[x]=dfn[x]=++tim; stack[++top]=x; for(int i=head[x];i;i=nextt[i]) { if((i^1)==pre) continue; int v=to[i]; if(!dfn[v]) { tarjan(v,i); low[x]=min(low[x],low[v]); } else low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { int k; sumcol++; do { k=stack[top--]; col[k]=sumcol; }while(k!=x); } } int main() { scanf("%d%d",&m,&n); for(int x,y;n--;) { scanf("%d%d",&x,&y); nextt[++cnt]=head[x];to[cnt]=y;head[x]=cnt; nextt[++cnt]=head[y];to[cnt]=x;head[y]=cnt; } for(int i=1;i<=m;++i) if(!dfn[i]) tarjan(i,-1); scanf("%d",&q); for(int x,y;q--;) { scanf("%d%d",&x,&y); if(col[x]==col[y]) printf("Yes "); else printf("No "); } return 0; }