hdu1269 有向图强连通分量 kosaraju 算法

本文主要是介绍hdu1269 有向图强连通分量 kosaraju 算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

迷宫城堡

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4943 Accepted Submission(s): 2175

Problem Description

为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。

Input

输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。

Output

对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。

Sample Input

Sample Output

  Yes
No
强连通分量的题！用专门的算法模板
这题用的是链表
 #include<cstdio>
#include<cstdlib>const int M=10005;struct node
{int vex;node *next;
};node *edge1[M],*edge2[M];bool mark1[M],mark2[M];int T[M],Tcnt,Bcnt;void DFS1(int x)
{mark1[x]=true;node *i;for(i=edge1[x];i!=NULL;i=i->next){if(!mark1[i->vex]){DFS1(i->vex);}}T[Tcnt]=x;Tcnt++;
}void DFS2(int x)
{mark2[x]=true;node *i;for(i=edge2[x];i!=NULL;i=i->next){if(!mark2[i->vex]){DFS2(i->vex);}}
}int main()
{int n,m;while(scanf("%d%d",&n,&m)){if(n==0&&m==0){break;}int i,a,b;for(i=1;i<=n;i++){mark1[i]=mark2[i]=false;edge1[i]=NULL;edge2[i]=NULL;}node *t;while(m--){scanf("%d%d",&a,&b);t=(node *)malloc(sizeof(node));t->vex=b;t->next=edge1[a];edge1[a]=t;t=(node *)malloc(sizeof(node));t->vex=a;t->next=edge2[b];edge2[b]=t;}Tcnt=0;for(i=1;i<=n;i++){if(!mark1[i]){DFS1(i);}}Bcnt=0;//Bcnt用于记录强连通分量的个数for(i=Tcnt-1;i>=0;i--){if(!mark2[T[i]]){DFS2(T[i]);Bcnt++;}}if(Bcnt==1)//如果强连通分量的个数为1则说明该图是强连通图{printf("Yes\n");}else{printf("No\n");}}return 0;
}

这篇关于hdu1269 有向图强连通分量 kosaraju 算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！