雖然搬家了，但新家還是有點問題，寫了這么半天的東西，先發到這里來吧。
其實以前求強連通分支都是用兩次深搜，沒有實現過Tarjan算法，其實寫起來都差不多了。只是細節上容易出現錯誤。在以下的代碼中我把容易錯的地方都標注了出來，方便以后查看。。
先貼個兩次深搜的代碼：
其中第一次是在原圖上進行深搜，第二次是在反向圖中按照第一次深搜結束時間遞減的順序搜索。這樣可以保證第二次搜索的時候每次找到一個強連通分支。
TWICE_DFS
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<int>u[101];
vector<int>v[101];
bool s[101];
bool noout[101],noin[101];
int stack[101];
int belong[101];
int n,m,indx;
int dfs1(int t)
{
if(s[t])
return 0;
s[t]=1;
int i;
for(i=0;i<u[t].size();i++)
{
dfs1(u[t][i]);
}
stack[++stack[0]]=t;
return 0;
}
int dfs2(int t)
{
if(s[t])
return 0;
s[t]=1;
int i;
for(i=0;i<v[t].size();i++)
{
dfs2(v[t][i]);
}
belong[t]=indx;
return 0;
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=1;i<=n;i++)
{
while(1)
{
scanf("%d",&m);
if(m==0)
break;
u[i].push_back(m);
v[m].push_back(i);
}
}
memset(s,0,sizeof(s));
for(i=1;i<=n;i++)
{
dfs1(i);
}
memset(s,0,sizeof(s));
for(i=stack[0];i>=1;i--)
{
if(!s[stack[i]])
{
indx++;
dfs2(stack[i]);
}
}
memset(noout,1,sizeof(noout));
memset(noin,1,sizeof(noin));
for(i=1;i<=n;i++)
{
for(j=0;j<u[i].size();j++)
{
if(belong[i]!=belong[u[i][j]])
{
noout[belong[i]]=0;
noin[belong[u[i][j]]]=0;
}
}
}
int res1=0,res2=0;
for(i=1;i<=indx;i++)
{
if(noout[i])
res2++;
if(noin[i])
res1++;
}
if(indx==1)
{
printf("1\n");
printf("0\n");
}
else
{
printf("%d\n",res1);
printf("%d\n",max(res1,res2));
}
system("pause");
return 0;
}
下面介紹一下Tarjan算法： Tarjan算法可以求無向圖的塊，割點，橋，也可以求有向圖的強連通分支，實現的細節不大一樣，但思想是一樣的，都是利用了搜索樹的性質，可以利用子節點的信息來更新父節點求得我們需要的信息。
low[i]代表由i節點可以達到的編號最小的結點，dfn[i]表示訪問的編號，對于無向圖，由于在無向圖的搜索中不會出現交叉邊，所以對節點i的子樹進行搜索后，假設i的兒子是j，則如果low[j]>dfn[i],則(i,j)為橋，如果i不是根節點，且low[j]>=dfn[i]或者i是根節點，且兒子數>1，則i為割點。
在有向圖中由于會出現交叉邊，所以我們不能像在求無向圖的連通分支那樣去在有向圖中進行搜索。怎樣保證求得強連通分支呢，我們可以用一個棧來保存連通分支中的結點，當確定一個連通分支之后退棧。
怎么求得連接兩個強連通分支的邊呢？low[j]>dfn[i]?這樣做是錯誤的，少考慮了一種情況。如果(i,j)是交叉邊，即在搜索i之前j已經搜索過，且j不是i的父節點，則(i,j)也為連接兩個強連通分支的邊。
(寫的我很沒有信心，不知道上面的文字對不對，如有錯誤請各位指正)
代碼如下：
Tarjan
#include<iostream>
#include<vector>
#define MAX 101
using namespace std;
vector<int>list[MAX];
int dfn[MAX],low[MAX];
int stack[MAX],instack[MAX];
int belong[MAX];
int Tuan=0;
int n;
int Index=0;
int indeg[MAX],outdeg[MAX];
int qiao[1000000][2];
int qiaonum;
int dfs(int u)
{
dfn[u]=low[u]=++Index;
int i;
stack[++stack[0]]=u;
instack[u]=1;
for(i=0;i<list[u].size();i++)
{
int v=list[u][i];
if(dfn[v]==0)
{
dfs(v);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])//如果沒訪問過v點，且low[v]>dfn[u]則邊(u,v)為連接兩個強連通分量的邊
{
qiao[++qiaonum][0]=u;
qiao[qiaonum][1]=v;
}
}
else //若已經訪問過v點
{
if(instack[v])//若不是交叉邊
{
low[u]=min(low[u],dfn[v]);
}
else //若是交叉邊：如果訪問過v點，且dfn[v]<low[u]則邊(u,v)為連接兩個強連通分量的邊
{
qiao[++qiaonum][0]=u;
qiao[qiaonum][1]=v;
}
}
}
if(low[u]==dfn[u])
{
Tuan++;
int j;
do{
j=stack[stack[0]--];
instack[j]=0;
belong[j]=Tuan;
}while(j!=u);
}
return 0;
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=1;i<=n;i++)
{
while(scanf("%d",&j)!=EOF&&j)
{
list[i].push_back(j);
}
}
for(i=1;i<=n;i++)
{
if(dfn[i]==0)
dfs(i);
}
for(i=1;i<=qiaonum;i++)
{
if(belong[qiao[i][0]]!=belong[qiao[i][1]])
{
outdeg[belong[qiao[i][0]]]++;
indeg[belong[qiao[i][1]]]++;
}
}
int cnt1=0,cnt2=0;
for(i=1;i<=Tuan;i++)
{
if(outdeg[i]==0)
cnt1++;
if(indeg[i]==0)
cnt2++;
}
if(Tuan==1)
{
printf("1\n");
printf("0\n");
}
else
{
printf("%d\n",cnt2);
printf("%d\n",max(cnt1,cnt2));
}
system("pause");
return 0;
}
PS：大家可以去看看
CmYkRgB123的講解，很詳細。 比我講的好。。。