强连通分量
题目：http://oj.我写了强连通分量，样例过了，但是还是好像有问题，请各位高手帮我看看
代码：
#include <stdio.h>
#include <stdlib.h>
int count=0;
void sort1(int t,int n,int mark[],int sign[],long map[100][100])
{
int i;
mark[t]=1;
for(i=0;i<n;i++)
if(map[t][i]==0&&mark[i]==0)
sort1(i,n,mark,sign,map);
sign[count++]=t;
}
void sort2(int t,int n,int mark[],int sign[],long map[100][100])
{
int i;
mark[t]=1;
for(i=0;i<n;i++)
if(map[i][t]==0&&mark[i]==0)
sort2(i,n,mark,sign,map);
}
int strong_connected(long map[100][100],int n)
{
int mark[100]={0},sign[100]={0};
int i,ans=0;
for(i=0;i<n;i++)
if(mark[i]==0)
sort1(i,n,mark,sign,map);
memset(mark,0,sizeof(mark));
for(i=n-1;i>=0;i--)
if(mark[sign[i]]==0)
{
ans++;
sort2(sign[i],n,mark,sign,map);
}
return ans;
}
int main()
{
long map[100][100];
int m,n,i,ans=0;
int start,end;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d %d",&start,&end);
map[start-1][end-1]=1;
}
ans=strong_connected(map,n);
printf("%d\n",ans);
system("pause");
return 0;
}
[ 本帖最后由 sunyh1999 于 2011-4-9 19:12 编辑 ]
