@Junlier
2018-10-25T21:59:19.000000Z
字数 1057
阅读 2744
知识点总结
阅读体验:https://zybuluo.com/Junlier/note/1322477
就是三个点构成的环
很简单,你是不是发现如果你知道三个点的连边方向了,那是不是可以判断是否为合法三元环
所以我们把有向图变无向,然后重新定向,向上边所讲的找出三元环,然后判断是否合法就了
复杂度不就是一样的吗,常数可能大一些
每两个点间都有连边的有向图
对于一个竞赛图,它要么是一个拓扑图,要么存在一个三元环。
说人话:一个竞赛图中如果存在环,则一定是三元环
随便自己在草稿纸上画几下就得证了,还是证一下吧
一些自己的瞎几把定义::有向边,:无向边
反证法:如果存在环且它不是三元环,那么会有三元组(都在大环上)存在边,那么考虑边的方向,如果是,那不就是三元环,伪掉,如果是,那么会得到一个把排除在外的小一点的环,那么递归证明,最后也是个三元环,伪掉,那么如果竞赛图中有环则一定是三元环
你当然可以用上面有向图求三元环的方法
但是对于竞赛图,我们有线性方法
先给出结论(圆括号是组合数,是一个点的出度)
直接选出三个点,那么就要容斥掉不是三元环的情况是吧
当然是这个三元环有一个点出度为啦,这样的三元组不可能构成环。。。
一些题目还会要求你容斥掉更多的情况,都可以考虑从点的度数那里入手吼