HDU 1269 迷宫城堡(强连通图)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1269

       一道判断强连通图的裸题，强连通图就是图中任意两点之间可以相互到达，直接用tarjan写就好了，直接求强连通分量，等于1就是Yes。

AC代码：

#include <bits/stdc++.h>
#define maxn 10005
#define maxm 100005
using namespace std;
struct Node{
	int to,next;
}Edge[maxm];
int head[maxn], num;
int dfn[maxn], low[maxn], cnt;
bool vis[maxn], flag;
int n, m, tot;

void init(){
	for(int i=0;i<=n;i++){
		low[i] = dfn[i] = 0;
		head[i] = -1;
		vis[i] = false;
	}
	flag = true;
	num = cnt = tot = 0;
}

void add(int u,int v){
	Edge[num].to = v;
	Edge[num].next = head[u];
	head[u] = num ++;
}

void tarjan(int x){
	dfn[x] = low[x] = ++ cnt;
	vis[x] = true;
	for(int i=head[x];i!=-1;i=Edge[i].next){
		int to = Edge[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[x] = min(low[x], low[to]);
		}
		else if(vis[to]){
			low[x] = min(low[x], dfn[to]);
		}
	}
	if(low[x] == dfn[x]){
		tot ++;
	}
}

int main()
{
	while(~scanf("%d%d",&n,&m)){
		if(n == 0 && m == 0) break;
		init();
		for(int i=0;i<m;i++){
			int u, v;
			scanf("%d%d",&u, &v);
			add(u, v);
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]) tarjan(i);
		}
		if(tot == 1) puts("Yes");
		else puts("No");
	}
	return 0;
}