hdoj 1269迷宮城(Kosarajuアルゴリズム、Tarjanアルゴリズム、Gabowアルゴリズム)

図の強連通解を求めます.
->Ksarajuアルゴリズム
    1.原図Gを深さ優先で巡回し、各点の出発時間を記録してスタックに入れる.
    2.スタックトップ要素を選択し、反図GTを巡回し、遍歴可能な点を削除し、これらの点は強い連結成分を構成する.
    3.もし頂点が削除されていないなら、サイクルステップ2、さもなければアルゴリズムは終了します.

#include
using namespace std;

int n,m,s;
int stak[10010],top;
vector edge[10010],edge_T[10010]; //     
bool vis[10010]; //         

void DFS_O(int v)
{
    vis[v] = true;
    for(int i=0; i0)
    {
        s = stak[--top];
        if(!vis[s])
        {
            DFS_T(s);
            ++cnt;//        +1
        }
    }
    return cnt;
}

int main()
{
    int a,b;
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&n==0)
            break;
        for(int i=1;i<=n;++i)
        {
            edge[i].clear();
            edge_T[i].clear();
        }
        for(int i=0;i

->Tarjanアルゴリズム
    1.アクセスされていないポイントvを探して、アルゴリズムがなければ終了します.
    2.初期化dfn[v]とlow[v]
        vの全隣接頂点u:
            ①訪問したことがないので、手順2に戻りながらlow[v]を維持する.
            ②訪問したが、削除されず、low[v]を維持する.
            low[v]==dfn[v]の場合、対応する強い連結成分が出力されます.               

#include
using namespace std;

#define ll long long
#define M 10010
int n,m;
vector edge[M];
int cnt;//       
int top;
int Index;
int dfn[M],low[M];// dfn[v]    v         low[v]   v         u low[v] low[u]    
int stak[M],Belong[M];//Belong[]                  
bool Instak[M];

void Init()
{
    cnt = top = Index = 0;
    for(int i=1;i<=n;i++)
        low[i] = dfn[i] = 0;
}

void Tarjan(int u)
{
    stak[top++] = u;
    Instak[u] = 1;
    low[u] = dfn[u] = ++Index;
    for(int i=0;i