http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=380#problem/B
这道题难在如何判断环与回路上,利用矩阵可区分出回路与环,即可做出此题
#include<stdio.h>
#include<string.h>
int relative[205][205],degree[205],answer[205];
void topologicalsort(int n){
int sign,i,j,k,temp;
for(i=n;i>=1;i–){
sign=0;
for(j=n;j>=1;j–)//若degree[j]==1,则该数顺序将被改变
if(degree[j]==0){
temp=j;
sign=1;
break;
}
if(sign==0)//判断是否连成线或回路与环(即矩阵中有对称的数值或值在对角线上)
break;
else{
degree[temp]–;
answer[temp]=i;
for(k=1;k<=n;k++)//若为回路或环,则无法改变排序顺序
if(relative[temp][k]!=0)
degree[k]–;
}
}
if(sign==0)//出线回路或环
printf(“-1\n”);
else{
for(i=1;i<n;i++)
printf(“%d “,answer[i]);
printf(“%d\n”,answer[n]);
}
}
int main(){
int n,a,b,m,t;
while(scanf(“%d”,&t)!=EOF){
while(t–){
memset(relative,0,sizeof(relative));
memset(degree,0,sizeof(degree));
scanf(“%d%d”,&n,&m);
while(m–){
scanf(“%d%d”,&a,&b);
if(relative[b][a]==0){
relative[b][a]=1;//一定要反着存,便于判断回路与否和换位
degree[a]++;
}
}
topologicalsort(n);
}

}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation