HOJ 1269 迷宫城堡（强连通分量tarjan算法，裸题）

强连通分量tarjan算法，裸题
本题要点：
1、题目要求，问有向图中，从任意一点是否能够到达其他的任意一点。
如果这图是强连通图，也就是强连通分量只有一个的时候，就能到到。
2、tarjan算法 求强连通分量
scc[i] 表示点i所在的强连通分量编号
sccnum 表示强连通分量编号
如果 sccnum == 1, 输出 Yes, 否则输出 No

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int MaxN = 10010, MaxM = 100010;
int head[MaxN], Next[MaxM], ver[MaxM];
int dfn[MaxN], low[MaxN], scc[MaxN], stk[MaxN], top, sccnum, indx;
int n, m, tot;void add(int x, int y)
{
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}void tarjan(int root)
{
    if(dfn[root])return;dfn[root] = low[root] = ++indx;stk[++top] = root;for(int i = head[root]; i; i = Next[i]){
    int v = ver[i];if(!dfn[v]){
    tarjan(v);low[root] = min(low[root], low[v]);}else if(!scc[v]){
    low[root] = min(low[root], dfn[v]);	}}if(low[root] == dfn[root]){
    sccnum++;while(true){
    int x = stk[top--];scc[x] = sccnum;	//x点属于哪个强连通分量if(x == root)break;}}
}int main()
{
    int x, y;while(scanf("%d%d", &n, &m) != EOF && (n != 0 || m != 0)){
    tot = indx = top = sccnum = 0;memset(head, 0, sizeof head);memset(scc, 0, sizeof scc);memset(dfn, 0, sizeof dfn);for(int i = 0; i < m; ++i){
    scanf("%d%d", &x, &y);add(x, y);}for(int i = 1; i <= n; ++i){
    if(!dfn[i])tarjan(i);}if(1 == sccnum){
    printf("Yes\n");}else{
    printf("No\n");}}return 0;
}/* 3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0 *//* Yes No */