poj 1094 Sorting It All Out(拓扑排序)

 

题意：

       给出一些字母和他们的大小关系， 然后给所有字母排序。会遇到三种情况：

1.      输入x( 1≤x ≤m)种关系后可以把所有顺序都确定。

2.      输入x( 1≤x ≤m)种关系后发现有矛盾

3.      全部都输入后都无法确定顺序

 

思路：

       每输入一种关系都要先判断下是否有矛盾， 有的话直接忽略后面的输入； 当所有该出现的字母都出现了时，判断是否可以确定顺序， 可以的话输出结果，忽略后面的输入， 否则继续输入关系，继续判断；输入完了都没有找到情况1，2，就可输出无法确定顺序。

       判断是否有矛盾，我也是用拓扑排序，与后面的拓扑排序不同的是前者入度为0的可以多个，后者只能有一个。

 

值得注意的地方是： 当情况1或者2任意一个满足时就可以忽略后面的了，我搞了半天就是以为在情况1满足的条件下，如果后面发现矛盾了，就以情况2处理。