POJ1094 Sorting It All Out (拓扑排序)

题意：

　　给你N个数，和M个关系，你需要通过这M个关系判断能否给这N个数排序，排序的原则类似于“<”运算符，如果a < b, b < c,那么 a < c；顺序的给出这N个数的关系，如果第 k 个关系和之前已经给出的 k-1 个关系矛盾(比如a < b, b < a)，那么就输出“Inconsistency found after k relations.”;如果通过第 k 个关系可以确定这N个数的排序序列(比如三个数，两个序列：a < b ,b < c)，那么输出“Sorted sequence determined after k relations: yyyyy.”,其中yyyyy是这N个数排序的结果;如果所有的关系给出后，既不矛盾，又不能确定惟一的一个序列(比如三个数，一个序列： a < b)，那么就输出“Sorted sequence cannot be determined.”

思路：

　　可以发现着有点类似于拓扑排序，那么这里就用拓扑排序来解决这道题。根据题意建图，如果a<b，那么点 a 到点 b 就建立一条有向边。这道题需要确定的是一个唯一的序列，所以如果能确定这个序列，那么所建起来的图肯定只有一个入度为0的点，作为这个序列的第一个点，之后删除这个点出发的所有边，然后剩下的图仍然只能有一个入度为零的点以供选取......即每次选择一个点后，然后删除其出发的有向边，剩下的图中只能有一个入度为0的点，才能保证序列唯一，总结下来，满足确定唯一序列的条件是：能对此图所有点进行拓扑排序，且拓扑排序序列唯一。然后需要判断是否成环，如果成环，那么对图运行一次拓扑排序算法之后，剩下的图中应该还有剩余的点，即在某时刻找不到入度为0的点供选择但已经排序的点不足总的点数。最后需要判断是否不能确定这个序列，这个条件只要排除掉上述两种情况就好了，即图中没有环且已经输出了图中的所有点，也就是给出的条件不足以确定这个序列。

注意：

　　如果通过第K个关系已经确定了这个序列，当出现第Z(Z>K)个关系又使得关系矛盾时，不认为其是矛盾的，因为已经确定序列了，就不用去考虑其他条件;反之亦然。

代码：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <stack>
 7 #include <queue>
 8 #include <algorithm>
 9 #include <string>
10 
11 typedef long long LL;
12 using namespace std;
13 const int MAXN = 26;
14 const int MAXM = 10000;
15 int indegree[MAXN + 7];//入度
16 int N, M;
17 
18 int head[MAXN + 7];//采用链式前向星存图 
19 typedef struct EdgeNode {
20     int to;
21     int next;
22 }Edge;
23 Edge edge[MAXM + 7];
24 
25 char ans[MAXN + 7];//答案序列
26 int len;
27 int tplgSort() {
28     int len = 0;
29     memset(ans, 0, sizeof(ans));
30     int indg[MAXN + 7] = {0};
31     for(int i = 0; i <= N; i++) indg[i] = indegree[i];//要进行多次拓扑排序算法，需保留原来的入度数组，新创一个数组进行操作
32     stack<int> st;//拓扑排序的辅助栈
33     for(int i = 1; i <= N; i++) {
34         if(!indg[i]) {//入度为0的进栈
35             st.push(i);
36         }
37     }
38     int ok = 1;
39     while(!st.empty()) {    
40         if((int) st.size() != 1) ok = 0;//每次进栈的数是否仅有一个，即当前图是否仅有一个入度为0的点存在
41         int tv = st.top();
42         ans[len++] = tv + 'A' - 1;
43         st.pop();
44         for(int k = head[tv]; k != -1; k = edge[k].next) {//选择一个点后，删除从这个点出发的所有有向边
45             if( !(--indg[edge[k].to]) ) {//删除之后如果入度为0,则进栈
46                 st.push(edge[k].to);
47             }
48         }
49     }
50     if(ok == 1 && len == N) return 1;//如果满足每次进栈的数仅有一个且已经生成全部序列，那么就已经确定这个序列了
51     else {
52         for(int i = 1; i <= N; i++) {
53             if(indg[i]) return -1;//如果剩余的图中还有剩余的点(若有剩余的点，则肯定存在入度不为0的点)
54         }
55         return 0;//剩余的图中没有点，且未生成全部序列
56     }
57 }
58 
59 int main() {
60     //freopen("input", "r", stdin);
61     //freopen("output", "w", stdout);
62     while(scanf("%d%d", &N, &M), N || M) {
63         memset(head, -1, sizeof(head));
64         memset(&edge, 0, sizeof(EdgeNode));
65         memset(indegree, 0, sizeof(indegree));
66         int index = -1, ok = 0;//index标记得出答案的关系号，ok表示当前状态
67         for(int i = 1; i <= M; i++) {
68             getchar();
69             char cu, cv;
70             cu = getchar(), getchar(), cv = getchar();
71             int u = cu - 'A' + 1, v = cv - 'A' + 1;
72             edge[i].to = v; //建图
73             edge[i].next = head[u];
74             head[u] = i;
75             ++indegree[v];
76             if(ok == 0) ok = tplgSort();//ok=0说明当前关系不能确定唯一序列
77             if( index < 0 && ok != 0)  index = i;//Ok!=0已经确定唯一序列或者出现矛盾关系，记录下标
78         }
79         if(ok == 0) printf("Sorted sequence cannot be determined.
");
80         else if(ok == 1) printf("Sorted sequence determined after %d relations: %s.
", index, ans);
81         else printf("Inconsistency found after %d relations.
", index);
82     }
83     return 0;
84 }