摘自百度:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现在v之前。
方法:
拓扑排序方法如下:
(1)从 中选择一个没有前驱(即 为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
例子:poj1094
解法: 摘自http://www.cnblogs.com/pushing-my-way/archive/2012/08/23/2652033.html
题意:给你一些大写字母间的偏序关系,然后让你判断能否唯一确定它们之间的关系,或者所给关系是矛盾的,或者到最后也不能确定它们之间的关系。
分析:
用拓扑排序:
1.拓扑排序可以用栈来实现,每次入栈的是入度为0的节点。
1.拓扑排序的结果一般分为三种情况:1、可以判断 2、有环出现了矛盾 3、条件不足,不能判断.
2.这道题不仅需要判断这三种情况,而且还要判断在处理第几个关系时出现前两种情况,对于本道题来说三种情况是有优先级的。前两种情况是平等的谁先出现先输出谁的相应结果,对于第三种情况是在前两种情况下都没有的前提下输出相应结果的.
网上对于这道题的错误提示:
1.本题顺序:
a.先判有没有环,有环就直接输出不能确定;
b.如果没有环,那么就看会不会有多种情况,如果有多种情况就再读下一行;如果全部行读完还是有多种情况,就是确定不了;
c.如果最后没有环,也不存在多种情况(即每次取出来入度为零的点只有一个),那么才是答案;
2.有答案就先出答案,不管后面的会不会矛盾什么的;
3.如果在没有读完所有输入就能出答案,一定要把剩下的行都读完。
1 View Code 2 #include3 #include 4 #include 5 #include 6 using namespace std; 7 //toposort的三种情况 8 //188K 0MS 9 const int N=27;10 int n,m;11 int graph[N][N],indegree[N],list[N];12 13 int toposort(int n)14 {15 int in[N];16 memcpy(in,indegree,sizeof(indegree)); //复制入度数组,以免对主函数中的indegree有影响17 stack s;18 int i;19 for(i=0;i 1)27 flag=1; //序列不确定28 t=s.top();29 s.pop();30 list[j++]=t; //记录出栈的数字31 for(i=0;i