# [ACM_模拟] POJ 1094 Sorting It All Out (拓扑排序+Floyd算法 判断关系是否矛盾或统一）

Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

Sample Input

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0


Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

b、如果没有环且每个点的出度+入度==n-1，则表明字母之间两两关系确定，构成唯一的一个序列，存在答案，否则不存在。

c、当答案存在时，利用拓扑排序确定各点顺序。

1 void Floyd(){
2      for(int k=1;k<=n;k++)
3          for(int i=1;i<=n;i++)
4              for(int j=1;j<=n;j++)
5                  if(dist[i][k]+dist[k][j]<dist[i][j])
6                      dist[i][j]=dist[i][k]+dist[k][j];
7 }

1 void Floyd(){
2      for(int k=1;k<=n;k++)
3          for(int i=1;i<=n;i++)
4              for(int j=1;j<=n;j++)
5                  if(dist[i][k]<INF && dist[k][j]<INF && dist[i][k]+dist[k][j]<dist[i][j])
6                      dist[i][j]=dist[i][k]+dist[k][j];
7 }

1 void Floyd(){
2      for(int k=1;k<=n;k++)
3          for(int i=1;i<=n;i++)
4              for(int j=1;j<=n;j++)
5                  if(dist[i][k] && dist[k][j])
6                      dist[i][j]=1;
7 }

b、拓扑排序：拓扑排序是对有向无环图(DAG图)的一种排序。表示了顶点按边的方向出现的先后顺序。如果有环，则无法表示两个顶点的先后顺序。

在现实生活中，也会有不少应用例子，比如学校课程布置图，要先修完一些基础课，才可以继续修专业课。

有向图可以拓扑排序的条件是：图中没有环。

具体方法：
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。

反复执行这两个步骤，直到所有结点都已经进入拓扑序列。

拓扑排序-离散数学-详解 http://sjjg.js.zwu.edu.cn/SFXX/tu/tu5.6.1.html

AC代码

 1 #include<iostream>
2 #include<cstdio>
3 #include<string.h>
4 #include<string>
5 #include<stack>
6 using namespace std;
7
8 #define maxn 30
9 int n,m;
10 bool map[maxn][maxn],visit[maxn];
11 int indegree[maxn],outdegree[maxn];
12 char str[maxn],ch[maxn];
13
14 bool Floyd(){
15     for(int i=0;i<n;i++)//Floyd对邻接矩阵的运算求可达矩阵
16         for(int j=0;j<n;j++)
17             for(int k=0;k<n;k++)
18                 if(map[j][i] && map[i][k])
19                     map[j][k]=1;
20     for(int l=0;l<n;l++)//判断是否成环
21         if(map[l][l])
22             return 0;
23     return 1;
24 }//Floyd算法对0-1邻接矩阵判断是否有环：map[i][i]=1
25
26 bool only_sure(){
27     memset(indegree,0,sizeof(indegree));
28     memset(outdegree,0,sizeof(outdegree));
29     for(int i=0;i<n;i++)//计算出度和入度
30         for(int j=0;j<n;j++)
31             if(map[i][j])
32                 indegree[j]++,outdegree[i]++;
33     for(int k=0;k<n;k++)//所有点出度入度之和均为n-1则说明所有关系确定
34         if(indegree[k]+outdegree[k]!=n-1)
35             return 0;
36     return 1;
37 }
38
39 //拓扑排序:从图中选择一个入度为0的点加入拓扑序列
40 //         从图中删除该结点以及它的所有出边(即与之相邻点入度减1)
41 void toplogical_sort(){
42     stack<int> Q;
43     int id=0;
44     for(int i=0;i<n;i++)
45         if(indegree[i]==0){
46             Q.push(i);
47             break;
48         }
49     memset(visit,0,sizeof(visit));
50     while(!Q.empty()){
51         int cur=Q.top();Q.pop();
52         visit[cur]=true;
53         str[id++]=cur+'A';
54         for(int j=0;j<n;j++){
55             if(!visit[j] && map[cur][j])indegree[j]--;//将所有子节点的入度-1
56             if(!visit[j] && indegree[j]==0)Q.push(j);
57         }
58     }
59     str[id]='\0';
60 }
61
62 int main(){
63     while(cin>>n>>m){
64         if(n==0 && m==0)break;
65         memset(map,0,sizeof(map));
66         int flag1=0;//标记矛盾出现时的步数
67         int flag2=0;//标记关系确认时的步数
68         for(int i=1;i<=m;i++){//边输入边检测
69             cin>>ch;
70             map[ch[0]-'A'][ch[2]-'A']=1;
71             if(flag1 ||flag2)continue;
72             else if(!Floyd())flag1=i;
73             else if(only_sure()){
74                 toplogical_sort ();
75                 flag2=i;
76             }
77         }
78         if (flag1) printf("Inconsistency found after %d relations.\n",flag1);
79         else if (flag2) printf("Sorted sequence determined after %d relations: %s.\n",flag2,str);
80         else printf("Sorted sequence cannot be determined.\n");
81     }return 0;
82 }

+ 订阅