给一个n个点,m条边的无向图,求该图與其补图的三元环个数.
能在考场上想出正解的人请受本蒟蒻一拜orz orz
首先考虑一个完全图,任意三个点都可以构成一个三元环.
所有的边都会在求原图的网站或者补图中出现.
当且仅当三元环中三条边都为求原图的网站边或补图边时这个三元环会在求原图的网站或补图中出现
所以不会茬求原图的网站或者补图中出现的环一定含有两种边
也就是∑(n-ki-1)*ki/2条边不会在求原图的网站和补图中出现
所以求原图的网站和补图中出现的环數和为
现在只需找到求原图的网站中环的个数
先求包含第一类点的三元环个数. 由于边很少,所以枚举2条边即可.由于一个点的度不超过sqrt(m),所以一條边最多被枚到(sqrt(m))次,最多枚M条边,所以这个操作时O(m*sqrt(m))的. 再求不包含第一类点的三元环个数. 由于每条边贡献2个度,所以二类点的数量是O(sqrt(m))级的.直接枚举彡个点,复杂度O((sqrt(m))^3)=O(m*sqrt(m)) 所以算法总的复杂度是O(m*sqrt(m))的.
有生之年noip考这种神奇的题目我直播吃键盘
