四元环统计

前置知识&＃xff1a;三元环统计

题意&＃xff1a;

给定无向图&＃xff0c;求图中四元环的数量。

解法&＃xff1a;

首先对图重定向&＃xff0c;重定向规则为度数大的指向度数小的&＃xff0c;度数相同时编号大的指向编号小的&＃xff0c;
这样构造出的新图一定是有向无环图。

四元环和三元环不同&＃xff0c;
主要体现在对于四元环&＃xff0c;有以下两种情况&＃xff1a;

对于右边的那种情况&＃xff0c;按照三元环那样的做法是枚举不到的。

观察发现两种四元环都有如下共性&＃xff0c;也就是四元环中最多只有一个点的出度为2&＃xff1a;

那么四元环可以被表示为&＃xff1a;

为了消除之前发现的两种四元环的影响&＃xff0c;下面部分考虑在无向图上枚举。

将每个点按照度数进行排名&＃xff0c;排名规则与重定向规则相同&＃xff0c;度数大的点排名大。

设点 i 的排名为rk[i]。

枚举点x&＃xff0c;枚举原图中x的相邻点y&＃xff0c;枚举新图中与y相邻的点z&＃xff0c;
如果rk[z]

原理&＃xff1a;

1.为什么需要rk[z] 因为两种合法的四元环&＃xff0c;一定是rk[z]
由上图&＃xff0c;x->y&＃xff0c;y->z&＃xff0c;因此rk[x]>rk[y]>rk[z]&＃xff0c;即rk[z]

同时也是为了防止以下不合法情况出现&＃xff1a;

如果不加判断&＃xff0c;可能会出现以上情况&＃xff0c;原因是下面部分是基于无向图枚举的。

复杂度&＃xff1a;

O(m*sq)