note: This article comes from http://www.byvoid.com/blog/scc-tarjan/. Please contact me via lethic@163.com if there is any infringement.
http://www.byvoid.com/blog/scc-tarjan/ lethic@163.com.

[]

G(strongly connected)GG(strongly connected components)

{1,2,3,4}1,2,3,4{5},{6}

image

O(N^2+M)KosarajuTarjanO(N+M)Tarjan

[Tarjan]

Tarjan

DFN(u)u()Low(u)uu

Low(u)=Min { DFN(u), Low(v),(u,v)uv DFN(v),(u,v)() }

DFN(u)=Low(u)u

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

tarjan(u)
{
    DFN[u]=Low[u]=++Index                      // uLow
    Stack.push(u)                              // u
    for each (u, v) in E                       // 
        if (v is not visted)               // v
            tarjan(v)                  // 
            Low[u] = min(Low[u], Low[v])
        else if (v in S)                   // v
            Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u])                      // u
        repeat
            v = S.pop                  // v
            print v
        until (u== v)
}

1DFSu=6DFN[6]=LOW[6]u=v{6}

image

5DFN[5]=LOW[5]{5}

image

344411LOW[4]=16(4,6)3(3,4)LOW[3]=LOW[4]=1

image

12(2,4)4LOW[2]=DFN[4]=51DFN[1]=LOW[1]{1,3,4,2}

image

{1,3,4,2},{5},{6}

TarjanO(N+M)

KosarajuKosarajuDFS O(N+M)TrajanKosarajuTarjanDFS TarjanKosaraju30%Tarjan()TarjanTarjanTarjan

TarjanRobert TarjanRobert TarjanTarjanTarjanTarjan

tarjanC++

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

void tarjan(int i)
{
    int j;
    DFN[i]=LOW[i]=++Dindex;
    instack[i]=true;
    Stap[++Stop]=i;
    for (edge *e=V[i];e;e=e->next)
    {
        j=e->t;
        if (!DFN[j])
        {
            tarjan(j);
            if (LOW[j]<LOW[i])
                LOW[i]=LOW[j];
        }
        else if (instack[j] && DFN[j]<LOW[i])
            LOW[i]=DFN[j];
    }
    if (DFN[i]==LOW[i])
    {
        Bcnt++;
        do
        {
            j=Stap[Stop--];
            instack[j]=false;
            Belong[j]=Bcnt;
        }
        while (j!=i);
    }
}
void solve()
{
    int i;
    Stop=Bcnt=Dindex=0;
    memset(DFN,0,sizeof(DFN));
    for (i=1;i<=N;i++)
        if (!DFN[i])
            tarjan(i);
}