哥們,我來你這里看看啊
1094 我錯了好多次啊 看看錯在哪里啊
//拓撲排序,鄰接陣形式,復雜度O(n^2)
//如果無法完成排序,返回0,否則返回1,ret返回有序點列
//傳入圖的大小n和鄰接陣mat,不相鄰點邊權0
#include<iostream>
using namespace std;
#define maxn 30
int mat[maxn][maxn],ret[maxn],d[maxn],n,num;
int stack[maxn*10];
bool stat[maxn];
bool toposort( )
{
int i,j,pos,top=0,t=0;
for(i=0;i<n;i++)
for(d[i]=j=0;j<n;j++)
if(mat[j][i]==1)d[i]++;
//memset(stack,-1,sizeof(stack));
for(top=i=0;i<n;i++)
if(!d[i]&&stat[i])
{
pos=i;t++;
}
if(t==1)stack[top++]=pos;
else if(t>1)return false;
while(top>0)
{
pos=stack[--top];
ret[num++]=pos;d[pos]=-1;
for(i=0;i<n;i++)
if(mat[pos][i]==1)d[i]--;
for(t=i=0;i<n;i++)
if(!d[i]&&stat[i])
{
pos=i;t++;
}
if(t==1)stack[top++]=pos;
else if(t>1) return false;
}
if(num==n)return true;
return false;
}
int main( )
{
int i,j,m,a,b;
char s[5],c; bool flag;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!m&&!n)break;
flag=true;num=0;
memset(ret,0,sizeof(ret));
memset(mat,0,sizeof(mat));
memset(stat,0,sizeof(stat));
for(i=1;i<=m;i++)
{
scanf("%s",s);
a=s[0]-'A';b=s[2]-'A';
stat[a]=true;stat[b]=true;
mat[a][b]=1;
if(toposort( )&&flag)
{
flag=false;
printf("Sorted sequence determined after %d relations: \n",i);
for(j=0;j<n;j++)
{
c=ret[j]+'A';
printf("%c",c);
}
printf("\n");
}
else
{
memset(ret,0,sizeof(ret));
num=0;
}
}
num=0;memset(ret,0,sizeof(ret));
toposort( );
if(!num&&flag)printf("Inconsistency found after %d relations.\n",m);
else if(num&&num<n&&flag)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}