這道題目的意思就是求一個有向圖有多少個強連通分量。求有向圖強連通分量的方法：（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 閱讀(353)
評論(2) 編輯 收藏 引用 所屬分類:
題目分類：圖論