三元环计数问题

今天考了道三元环计数发现自己完全不会……赶紧补补。

无向图三元环计数

• 统计每个点的度数，对于一条无向边$<u,v>$，若$d_u=d_v$则从编号小的点向编号大的点连有向边，否则从$d$较小的向较大的点连有向边。
• 这样无向图就变为了一个$DAG$模型，然后扫一下每个点$u$，对其出点$v$打标记$vis_v=u$，再对每个出点$v$的出点$w$判断是否满足$vis_w=u$即可。
• 这样定向后可以保证是个有向无环图。
• 为什么呢，要想定向存在环，则这个环上的点度数必须相同，由于保证了编号从小到大走，所以不存在。
• 复杂度：$m\sqrt m$
• 分别分析度数小于等于$\sqrt m$的点和大于的点即可证明。

有向图三元环计数

• 其实和无向图差不多，转化成无向图后重定向，因为三元环个数不超过$m\sqrt m$，所以可以把所有三元环全部找出来，然后暴力判断。
• 复杂度同上。

竞赛图的三元环计数

• 竞赛图的三元环计数存在线性算法。
• 对于一个竞赛图，它要么是一个拓扑图，要么存在一个三元环，具体证明比较显然……。
• 对于任意一个竞赛图的三元环计数存在一个线性的容斥做法，考虑总共的三元环为$C_{n}^{3}$，对于第$i$个点出度集合为$P_i$，显然对于三元组$(i,x,y)$且$x,y$属于$P_i$，那么一定不组成三元环，而且这样的三元组只会在第$i$点枚举一次。
• 所以答案就是：
  $$C_{n}^{3}-\sum C_{|P_i|}^{2}$$
• 直接算即可。