HDU 1269 迷宫城堡 （有向图强连通分量Tarjan）

题意：给定有向图，判断是否为强连通图。

思路：方法很简单，直接Tarjan求图强连通分量个数是否为一即可。主要是把Tarjan模板附上来以后好整理。。。

Byvoid的Tarjan算法讲解很详细：https://www.byvoid.com/blog/scc-tarjan/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stack>
#define NODENUM 10005
#define EDGENUM 100005
using namespace std;

int N,M;

struct edgenode
{
    int to,next;
}Edge[EDGENUM];
int head[NODENUM],edgenum;

bool in[NODENUM];
stack<int> S;
int rn,dfn[NODENUM],low[NODENUM],index;


void init()
{
    memset(head,-1,sizeof(head));
    memset(in,0,sizeof(in));
    memset(dfn,0,sizeof(dfn));
    index=rn=edgenum=0;
    while(!S.empty()) S.pop();
}

void add(int a,int b)
{
    ++edgenum;
    Edge[edgenum].next = head[a];
    Edge[edgenum].to = b;
    head[a] = edgenum;
}

void build()
{
    while(M--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
    }
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++index;
    S.push(u); in[u]=1;
    
    for(int p=head[u];~p;p = Edge[p].next)
    {
        int i = Edge[p].to;
        if(!dfn[i])
        {
            tarjan(i);
            low[u] = min(low[u],low[i]);
        }
        else if(in[i]) low[u] = min(low[u],low[i]);
    }
    
    if(dfn[u] == low[u])
    {
        ++rn;
        int v;
        do
        {
            v = S.top();
            S.pop();
            in[v]=0;
        }
        while(u!=v);
    }
}

void work()
{
    for(int i=1;i<=N;++i)
        if(!dfn[i]) tarjan(i);
    printf("%s\n",rn == 1? "Yes":"No");
}

int main()
{
    while(~scanf("%d %d",&N,&M) && N+M)
    {
        init();
        build();
        work();
    }
    return 0;
}

HDU 1269 迷宫城堡 （有向图强连通分量Tarjan）,布布扣,bubuko.com

HDU 1269 迷宫城堡 （有向图强连通分量Tarjan）

原文：http://blog.csdn.net/blzorro/article/details/19963715