这道题目的意思就是求一个有向图有多少个强连通分量。求有向图强连通分量的方法：（1）做正向dfs，即如果用g[i][j]==1表示i结点到j结点有一条边，那么就是从i结点到j结点的遍历，在dfs函数的最后加上这么两行代码：count++;finish[count]=now；now表示当前所在dfs函数的结点。finish数组记录退出dfs函数的顺序。（2）按照finish数组中记录值的顺序做逆向dfs，即如果i结点到j结点有边，那么做从j到i的遍历。
以下是我的代码，我把正向dfs和逆向dfs写在了一个函数里：
#include<stdio.h>
#define MAXN 201
long n,ans,count,g[MAXN][MAXN],finish[MAXN],visit[MAXN];
void init()
{
long i,j,tmp;
scanf("%ld",&n);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
g[i][j]=0;
for(i=1;i<=n;i++)
{
scanf("%ld",&tmp);
while(tmp!=0)
{
g[i][tmp]=1;
scanf("%ld",&tmp);
}
}
}
void dfs(long now,long bj)
{
long i;
visit[now]=1;
switch(bj)
{
case 1:
for(i=1;i<=n;i++)
if(g[now][i]==1&&!visit[i])
{
visit[i]=1;
dfs(i,bj);
count++;
finish[count]=now;
break;
case 2:
for(i=1;i<=n;i++)
if(g[i][now]==1&&!visit[i])
{
visit[i]=1;
dfs(i,bj);
}
}
}
void run()
{
long i;
count=0;
ans=0;
for(i=0;i<=n;i++)
visit[i]=0;
for(i=1;i<=n;i++)
if(!visit[i])
dfs(i,1);
for(i=0;i<=n;i++)
visit[i]=0;
for(i=n;i>=1;i--)
if(!visit[finish[i]])
{
ans++;
dfs(finish[i],2);
}
printf("%ld\n",ans);
}
int main()
{
init();
run();
return 0;
}
posted on 2010-01-06 20:02
lee1r 阅读(340)
评论(2) 编辑 收藏 引用 所属分类:
题目分类：图论