bzoj1098

题意

求补图的连通块个数

做法

起初(S,T)是全集

• ((1))：若(S)非空，从(S)中弹出一个点，将其加入空集(A)，将其弹出(T)，进行((2))操作；否则退出
• ((2))：若(A)非空，弹出任意点(x)，进行((3))操作；否则返回((1))
• ((3))：将(x)在原图中的邻点在(T)内的弹出，将(T)内的点加入(A)弹出(S)，清空(T)，将从(T)中弹出的邻点加入。返回((2))

用链表维护，(O(n+m))，感觉讲得好抽象啊。。要是看不懂随便扒份代码看吧，就不放了

做法二

upd 11.19：发现一种更直观的方法
考虑补图中点数最大的点，度数为(O(n-frac{m}{n}))
将这些点缩起来后，点数为(O(n-(n-frac{m}{n}))=frac{m}{n})
那么点对暴力建边，这部分复杂度(O(frac{m^2}{n^2}))
通过计算大概复杂度是(O(n+m))的