[CF920E] Connected Components?

题目链接:Connected Components?

Description

一句话题意:求一张图的补图的连通块数。
给定一张 \(n\) 个点,\(\frac{n\times (n-1)}{2}-m\) 条边的无向图。
读入 \(m\) 对点,表示不存在 \(u\) 到 \(v\) 这条边。
问这张图中有多少个连通块,并且将连通块的个数按不降序输出。
数据范围 \(1\le n\le 200000, 0\le m\le min(\frac{n\times (n-1)}{2}, 200000)\)

Solution

由抽屉原理知,必定存在一个点,与它相关的删去的边有\(\frac{m}{n}\)条。
我们找到这个点,然后将所有与它存在连边的点相连。显然,此时只剩下\(\frac{m}{n}\)个点还没有被匹配过。
对于剩下这些点,我们暴力枚举它们所连向的边即可。
复杂度 \(O(\frac{m}{n} \times n) = O(n)\)

Code

上一篇:R 《回归分析与线性统计模型》page120,4.3


下一篇:zookeeper not connected