poj 1094 Sorting It All Out (拓补）

代码：
View Code
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int map[30][30];
 6 int de[30];
 7 int res[30];//存储结果
 8 int n,m;
 9 int topo()
10 {
11     int i,j;
12     int d[30];
13     int num,pos;
14     int k=0,t=1;
15     for(i=1;i<=n;i++)
16     {
17         d[i]=de[i];
18     }
19     for(i=1;i<=n;i++)
20     {
21         num=0;
22         for(j=1;j<=n;j++)
23         {
24             if(d[j]==0)
25             {
26                 num++;//入度为0的点的个数
27                 pos=j;//入度为0的点的位置
28             }
29         }
30         if(num==0&&num!=n)
31         return 0;//入度为0的点为0，存在环
32         if(num>1)//是否存在唯一的入度为0点
33         t=-1;
34         res[k]=pos;
35         k++;
36         d[pos]=-1;
37         for(j=1;j<=n;j++)//更新
38         {
39             if(map[pos][j]==1)
40             d[j]--;
41         }
42     }
43     return t;
44 }
45 int main()
46 {
47     int i,j;
48     char str[10];
49     while(scanf("%d%d",&n,&m)!=EOF)
50     {
51         if(m==0&&n==0)
52         break;
53         getchar();
54         memset(de,0,sizeof(de));
55         memset(map,0,sizeof(map));
56         int flag=0;
57         int t;
58         for(i=1;i<=m;i++)
59         {
60             gets(str);
61             map[str[0]-'A'+1][str[2]-'A'+1]=1;
62             de[str[2]-'A'+1]++;
63             if(flag==0)//关系是否已判断出
64             t=topo();//每输入一个关系进行一次拓补
65             if(flag==0&&t==0)//存在环，输出矛盾
66             {
67                 printf("Inconsistency found after %d relations.\n",i);
68                 flag=1;
69             }
70             if(flag==0&&t==1)//最终有n个顶点且无环
71             {
72                 printf("Sorted sequence determined after %d relations: ",i);
73                 for(j=0;j<n;j++)
74                     printf("%c",res[j]+'A'-1);
75                 printf(".\n");
76                 flag=1;
77             }
78         }
79         if(flag==0)
80             printf("Sorted sequence cannot be determined.\n");
81 
82     }
83     return 0;
84 }