今天考了道三元环计数发现自己完全不会……赶紧补补。
无向图三元环计数
- 统计每个点的度数，对于一条无向边(<u,v>)，若(d_u=d_v)则从编号小的点向编号大的点连有向边，否则从(d)较小的向较大的点连有向边。
- 这样无向图就变为了一个(DAG)模型，然后扫一下每个点(u)，对其出点(v)打标记(vis_v=u)，再对每个出点(v)的出点(w)判断是否满足(vis_w=u)即可。
- 这样定向后可以保证是个有向无环图。
- 为什么呢，要想定向存在环，则这个环上的点度数必须相同，由于保证了编号从小到大走，所以不存在。
- 复杂度：(msqrt m)
- 分别分析度数小于等于(sqrt m)的点和大于的点即可证明。
有向图三元环计数
- 其实和无向图差不多，转化成无向图后重定向，因为三元环个数不超过(msqrt m)，所以可以把所有三元环全部找出来，然后暴力判断。
- 复杂度同上。
竞赛图的三元环计数
- 竞赛图的三元环计数存在线性算法。
- 对于一个竞赛图，它要么是一个拓扑图，要么存在一个三元环，具体证明比较显然……。
- 对于任意一个竞赛图的三元环计数存在一个线性的容斥做法，考虑总共的三元环为(C_{n}^{3})，对于第(i)个点出度集合为(P_i)，显然对于三元组((i,x,y))且(x,y)属于(P_i)，那么一定不组成三元环，而且这样的三元组只会在第(i)点枚举一次。
- 所以答案就是：
[C_{n}^{3}-sum C_{|P_i|}^{2}
]
- 直接算即可。