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}

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

 ```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}

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

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

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

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

TarjanO(N+M)

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

TarjanRobert TarjanRobert TarjanTarjanTarjanTarjan

tarjanC++

 ```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]