虽然搬家了，但新家还是有点问题，写了这么半天的东西，先发到这里来吧。
其实以前求强连通分支都是用两次深搜，没有实现过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的讲解，很详细。 比我讲的好。。。