【HDU 4324】Triangle LOVE(拓扑排序)

26
Sep

【HDU 4324】Triangle LOVE(拓扑排序)

很久没有更博客了,其中又很重要的一个原因是因为自己懈怠了下来,另一方面也是因为准备将拓扑排序这个部分的题目都做一些以后再更,现在就记录在这里。

题面描述
给定一个01矩阵a,如果a[i][j]等于0,那么存在一条从j连向i的边,不存在二元环。求问给定图中是否存在三元环。
解题思路
首先要推导一个结论:我们设现在存在一个大于三元的环,那么我们从这个环中选取三个连续的元素i,j,k,并令其连接顺序为i->j->k,因为如果i,j,k不能构成三元环,那么必有i->k,则我们就可以从这个环中删去元素j并保持剩下元素依然成环。如此重复,必定最终能构成三元环。又因为图中不存在二元环,因此得到结论:命题成立的条件等价于图中存在环,即不能被拓扑排序。
代码编写
由于输入数据量很大,因此需要用scanf/printf;其他部分只要构建一个图然后调用拓扑排序即可。

AC代码
https://paste.ubuntu.com/25616260/

由于个人水平有限,上述文字可能存在错误,如有问题,欢迎指正和讨论!

添加新评论