HDU - 1269
| 时限: 1000MS | 内存: 32768KB | 64位IO格式: %I64d & %I64u |
问题描述
为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。
输入
输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。
输出
对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。
样例输入
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
样例输出
Yes
No
来源
HDU 2006-4 Programming Contest
分析
裸的Tarjan = =
代码
1 #include2 #include 3 #include 4 #define maxn 1000000 5 using namespace std; 6 7 struct edge{ 8 int from,v; 9 }e[maxn];10 11 int tot,first[maxn];12 void insert(int u,int v){13 tot++;14 e[tot].from = first[u];15 e[tot].v = v;16 first[u] = tot;17 }18 19 bool vis[maxn];20 int color[maxn],n,m,dfn[maxn],low[maxn],TIM,COL,top,stack[maxn];21 22 void Tarjan(int p){23 dfn[p] = low[p] = ++TIM;24 vis[p] = true;25 stack[++top] = p;26 for(int i = first[p];i;i = e[i].from){27 int v = e[i].v;28 if(!dfn[v]){29 Tarjan(v);30 low[p] = min(low[p],low[v]);31 }else if(vis[v]) low[p] = min(low[p],dfn[v]);32 }33 34 if(dfn[p] == low[p]){35 ++COL;36 color[p] = COL;37 vis[p] = false;38 while(stack[top] != p){39 color[stack[top]] = COL;40 vis[stack[top--]] = false;41 }42 top--;43 }44 45 // printf("dfn[%d]: %d low[%d]: %d\n",p,dfn[p],p,low[p]);46 47 }48 49 int main(){50 51 while(1){52 memset(color,0,sizeof(color));53 memset(dfn,0,sizeof(dfn));54 memset(low,0,sizeof(low));55 memset(first,0,sizeof(first));56 tot = COL = TIM = top = 0;57 scanf("%d%d",&n,&m);58 59 if(!n && !m) return 0;60 61 int a,b;62 for(int i = 1;i <= m;i++){63 scanf("%d%d",&a,&b);64 insert(a,b);65 }66 67 for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i);68 69 if(COL == 1) printf("Yes\n",COL);70 else printf("No\n");71 }72 73 74 return 0;75 }