nyoj349 Sorting It All Out(拓扑排序)

nyoj349 Sorting It All Out(拓扑排序)

题目349​​题目信息​​​​运行结果​​​​本题排行​​​​讨论区​​

Sorting It All Out

3000 ms  |  内存限制： 65535

3

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 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.

输出 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.

样例输入

4 6 A

样例输出

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

来源 ​​POJ​​

上传者 ​​陈玉​​

刚开始没有理解题意 。。想了好两三天 哈哈（好吧 是我懒了）

拓扑排序过程：

1先建图，然后寻找入读为0的顶点

2：然后找到与这个顶点有关的边和点，删去边，点的入度-1

3.继续寻找下一个入度为0的顶点。。重复2.

总共三种情况 冲突 可以排序 信息不完整

判断冲突 起初我想错了 总想着并查集判断成环冲突 可以却发现我错的大大的 因为并查集判断的是集合  也就是无向的

而这道题是有向的。

比如A

其中判断冲突 实在输入的时候就判断的 可以排序和信息不完整在输入数据完毕后再检查。

拓扑排序处理信息不完整和冲突

1.如果出现两个同时入度为0的，并且根是自己就是信息不完整。

2.如果栈的大小刚好等于比较的数的个数 那么就是能够排序 如果栈的大小小于比较的数的个数 就是信息不完整

用的vector容器模拟邻接表。queue实现拓扑排序，stack存贮大小

#include #include #include #include #include using namespace std;vectormap[27];//邻接表 int degree_in[27];//顶点的入度 bool have[27],vis[27];//hava判断是否是比较的数 ，vis是在判断成环的时候 判断是否已经遍历 stacks; //拓扑排序 int top_sort(int n){ queuetemp; int pos; while(!s.empty()) s.pop(); while(!temp.empty()) temp.pop(); for(int i=0;i<26;i++) { if(degree_in[i]==0&&have[i]) { temp.push(i); have[i]=false; } } while(!temp.empty()) { if(temp.size()>1) return 1; pos=temp.front(); temp.pop(); s.push(pos); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。