链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1269
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=86270#problem/A
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<iostream> 5 #include<algorithm> 6 #include<cstring> 7 #include<vector> 8 using namespace std; 9 #define maxn 10005 10 11 int dfn[maxn];///代表最先遍历到这个点的时间 12 int low[maxn];///这个点所能到达之前最早的时间点 13 int Stack[maxn];///自定义的栈，比较好用 14 int cnt, bloks;///cnt总的连通个数， 连通块的总个数 15 bool InStack[maxn];///判断这个点是否在栈中 16 int n, m, Time, top;///Time 时间点， top用于栈操作 17 vector<vector<int> > G; 18 19 void Tarjan(int u) 20 { 21 low[u] = dfn[u] = ++Time;///更新时间点 22 Stack[top++] = u;///将u压入栈中 23 InStack[u] = true; 24 int len = G[u].size(), v;///深度优先遍历与u相连的所有节点 25 26 for(int i=0; i<len; i++) 27 { 28 v = G[u][i]; 29 30 if(!dfn[v])///我们可以用dfn判断这个点是否曾经被遍历过 31 {///若是没被遍历过，那么我们就遍历一下 32 Tarjan(v); 33 ///假如u点下方节点v可以到达的点那么u点也一定能到达 34 low[u] = min(low[u], low[v]); 35 ///在两者中取一个最小的，到达点 36 } 37 else if( InStack[v] ) 38 /**如果遍历的这个点已经在栈中了，那么就需要更新一下，这里其实写成low[u] = min(low[u],low[v])也可以肯定是没错的，但是 39 在我们求割点的时候就必须要写成low[u] = min(low[u], dfn[v])，到求割点的时候我们会好好解释一下*/ 40 low[u] = min(low[u], dfn[v]); 41 } 42 /**当这个节点的所有节点已经遍历完了并且 low[u] == dfn[u]，这个时候说明我们已经返回到了这个点的最初的时间点的位置 43 将我们栈中的所有元素出栈就可以完成连通图求解了*/ 44 if(low[u] == dfn[u]) 45 { 46 do 47 { 48 cnt ++; 49 v = Stack[--top]; 50 InStack[v] = false; 51 }while(u != v); 52 bloks ++; 53 } 54 } 55 void Init() 56 { 57 G.clear(); 58 G.resize(n+1); 59 memset(low, 0, sizeof(low)); 60 memset(dfn, 0, sizeof(dfn)); 61 memset(Stack, 0, sizeof(Stack)); 62 memset(InStack, false, sizeof(InStack)); 63 bloks = cnt = Time = top = 0; 64 } 65 66 int main() 67 { 68 while(scanf("%d %d",&n, &m), n+m) 69 { 70 Init(); 71 while(m --) 72 { 73 int a, b; 74 scanf("%d %d", &a, &b); 75 G[a].push_back(b); 76 } 77 Tarjan(1); 78 if( cnt == n && bloks == 1 ) 79 puts("Yes"); 80 else 81 puts("No"); 82 } 83 return 0; 84 }