D:0-1 Mst
传送门:https://codeforces.com/contest/1243/problem/D
题意:
给你一个图,问你它的补图的连通块的个数,
思路:
首先,联通块的个数,就是集合的个数.我们考虑用并查集维护集合。对于一张图,共n个点,假设前m个点已经被并成k个集合。用一个vector维护这些集合的父节点(我们用集合中的父节点来表征不同集合)。
现在新增第m + 1个点,我们考虑这个点能添加到哪个集合中去。
对于这个点,遍历它所有的边,只考虑终点编号比他小的那些点(由于每条边都是双向的,所以编号比他大的点之后会反过来考虑现在这个点),然后找这些点所在集合的父节点,用一个map,Q[i] 代表现在这个点和集合i所连的边数。那么当且仅当(这个点和集合i所连的边数) == (当前这个集合的大小) 时,这个点不能归并到这个集合中去.
所以我们还要开一个size数组维护集合的点数的大小
总的来说,还是利用了动态规划(分阶段进行)的思想,哎什么时候才能贯彻这个思想呢。。。
复杂度:
AC代码:
https://codeforces.com/contest/1243/submission/70351813