[奇葩方法]三元环题解_小奇和小偶在玩游戏。从前有个包含个点, 条边,无自环和重边的无向图。对于两个

作者：笔触狂放9 | 2024-02-06 21:17:11

踩

小奇和小偶在玩游戏。从前有个包含个点, 条边,无自环和重边的无向图。对于两个

[题目描述]

给你一个包含n个点,m条边的无向图,求三元环个数.

[数据范围]

n,m<=200000

[题解]

这个方法是lypYY出的一个奇葩方法.ORZlyp,YY都能YY出这种方法.

将所有点分成两类:度数<sqrt(m)的和度数>sqrt(m)的.

先求包含第一类点的三元环个数.

由于边很少,所以枚举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))的.

再次ORZlyp的神犇做法,我这种弱菜什么时候才能脱菜啊....

BY QW

转载请注明出处

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/64603

[奇葩方法]三元环题解_小奇和小偶在玩游戏。 从前有个包含 个点, 条边,无自环和重边的无向图。 对于两个