[讨论]根据一组序列可否判断是可拓扑的?
如题,如果已知一组序列,能否判断这组序列可以由一个有向无环图
通过拓扑排序产生?
[解决办法]
这个序列没有其它条件了吗?
[解决办法]
我说的环指的是链构成的有方向的环.
恩,让想想吧怎么做。
计算可达距证吧。
(1)X,A,B,Y
X->A X->B X->Y A->B A->Y B->Y可达
如果其中任意一个的相反也可达的话,则说明不能 拓扑排序产生
每往里面添加一组序列就是在增加可达链的条数。
只要里面没有相反的可达,就OK,否则,不OK、