https://www.byvoid.com/blog/scc-tarjan
主要思想
Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，
Low(u)=Min
{
DFN(u),
Low(v),(u,v)为树枝边，u为v的父节点
DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)
}
当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。
因此很容易理解..
算法伪代码如下
tarjan(u)
{
DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
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)
}
C++代码：
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);
}
自己的版本：
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <stack>
using namespace std;
int N,M;
string NAME[40];
map<string,int> dict;
stack<int> S;
int tot=0; //这一道题特有的存点..
int cnt=0; //强连通数目
int time=0; //时间戳
int DFN[40],Low[40]; //DNF 时间戳,Low ,u及u的子树最小的时间戳
bool INSTACK[40]; //判断是否在栈内
int Belong[40]; //存储属于哪一个强连通分量;
struct Edge{
int to;
Edge *next;
}E[20000],*EE;
struct Node{
Edge *first;
}G[50];
void Link(int a,int b)
{
EE->to=b;EE->next=G[a].first;G[a].first=EE++;
}
void input()
{
EE=E;
tot=0;
time=0;
cnt=0;
string a,b;
dict.clear();
memset(G,0,sizeof(G));
memset(DFN,0,sizeof(DFN));
for(int i=1;i<=M;i++)
{
cin>>a>>b;
if(dict[a]==0)
{
dict[a]=++tot;
NAME[tot]=a;
}
if(dict[b]==0)
{
dict[b]=++tot;
NAME[tot]=b;
}
Link(dict[a],dict[b]);
}
}
void Tarjan(int u)
{
DFN[u]=Low[u]=++time;
S.push(u);
INSTACK[u]=true;
for(Edge *p=G[u].first;p;p=p->next)
{
if(DFN[p->to]==0)
{
Tarjan(p->to);
Low[u]=min(Low[u],Low[p->to]);
}
else if(INSTACK[p->to]==true)
Low[u]=min(Low[u],DFN[p->to]);
}
int k;
if(DFN[u]==Low[u])
{
int ok=0;
cnt++;
do
{
k=S.top();
S.pop();
INSTACK[k]=false;
Belong[k]=cnt;
if(ok==0)
{
ok=1;
cout<<NAME[k];
}
else cout<<", "<<NAME[k];
}while(k!=u);
cout<<endl;
}
}
void solve()
{
for(int i=1;i<=N;i++)
{
if(DFN[i]==0)
Tarjan(i);
}
}
int main()
{
int CASE=0;
// freopen("a.in","r",stdin);
while(cin>>N>>M&&(N||M))
{
printf("Calling circles for data set %d:\n",++CASE);
input();
solve();
}
}