HDU1269 迷宫城堡

时间：2022-08-27 14:23:55

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

 
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

3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
 

Sample Output

Yes
No
 
 
正解：tarjan
解题报告：
　　tarjan算法裸题，check一下全图是否有且仅有一个强连通分量。
　　联赛前复习模板...
 
 //It is made by ljh2000

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 #include <string>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 int n,m,ecnt,first[MAXN],to[MAXM],NEXT[MAXM];

 int dfn[MAXN],low[MAXN],cnt,zhan[MAXN],top;

 bool pd[MAXN];

 inline int getint(){

     int w=,q=; char c=getchar(); while((c<''||c>'') && c!='-') c=getchar();

     if(c=='-') q=,c=getchar(); while (c>=''&&c<='') w=w*+c-'',c=getchar(); return q?-w:w;

 }

 inline void tarjan(int x){

     dfn[x]=low[x]=++ecnt; zhan[++top]=x; pd[x]=;

     for(int i=first[x];i;i=NEXT[i]) {

         int v=to[i];

         if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);

         else if(pd[v]) low[x]=min(low[x],dfn[v]);

     }

     if(dfn[x]==low[x]) {

         cnt++;    while(zhan[top]!=x) pd[zhan[top]]=,top--;

         pd[x]=; top--;

     }

 }

 inline void work(){

     while() {

         n=getint(); m=getint(); int x,y; if(n== && m==) break;

         memset(first,,sizeof(first)); ecnt=;

         for(int i=;i<=m;i++) {    x=getint(); y=getint();    NEXT[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; }

         memset(dfn,,sizeof(dfn)); memset(low,,sizeof(low)); ecnt=;

         cnt=; for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i);

         if(cnt!=) printf("No\n"); else printf("Yes\n");

     }

 }

 int main()

 {

     work();

     return ;

 }

相关文章