这个题,第一次做的时候,感觉好麻烦,
那个时候,不怎么清楚拓扑排序。
所以,那个时候借鉴网友的代码,用到了Floyd。
拓扑排序就是
1、找入度为0的点
2、将入度为0的点输出,然后将这点的出边全部删了。
3、继续循环。
现在想来感觉真的麻烦多了。 于是自己亲手来A。
题目的大意明了:
每输入一组数据,就用拓扑排序一次。
如果排序出来了。 就保存这个值。也就是在第 i 组数据时,确定了顺序。后面的数据直接读取就行,不用管了,到时候直接输出序列,和那个 i 值。
如果排序不出,出现了环。那么也和上面一样处理。
如果这两个结果都不是,那么就是不确定序列。
这个看起来确实蛮简单。
测试数据的话 Discuss 里面有。
下面直接贴代码吧
#include <stdio.h> #include <stdlib.h> #include<string.h> #define N 27 int indegree[N];//存入度 int map[N][N];//存图 int stack[N];//存序列 int count; int n,m; int topsort() { int i,j=0; int num0,flag=0; int num=0,in[N]; for(i=1; i<=n; i++) in[i]=indegree[i]; count=0; while(1) { num0=0; j=0; for(i=1; i<=n; i++) { if(in[i]==0) { num0=i; j++;//这个是用来判断入度为0的点有多少个。如果有大于1个的话就是不确定序列 } } if(num0) { num++; in[num0]--; stack[count++]=num0; if(j>1&&flag!=-1)flag=-1; for(i=1; i<=n; i++) { if(map[num0][i]) { in[i]--; } } } else break; } if(num!=n)return 0; if(flag==-1)return -1; return 1; } int main() { int i,flag,num,j=0; char s[4]; while(1) { scanf("%d %d",&n,&m); if(n==0&&m==0)break; memset(map,0,sizeof(map)); memset(indegree,0,sizeof(indegree)); num=0; j=0; for(i=1; i<=m; i++) { scanf("%s",s); if(!j&&!map[s[0]-'A'+1][s[2]-'A'+1]) { map[s[0]-'A'+1][s[2]-'A'+1]=1; indegree[s[2]-'A'+1]++; flag=topsort(); if(flag==0) { j=1; num=i; } if(flag==1&&num==0) { num=i;j=1; } } } if(flag==0) { printf("Inconsistency found after %d relations.\n",num); continue; } if(flag==1) { printf("Sorted sequence determined after %d relations: ",num); for(i=0; i<count; i++) { printf("%c",'A'+stack[i]-1); } printf(".\n"); continue; } printf("Sorted sequence cannot be determined.\n"); } return 0; }