1098: [POI2007]办公楼biu
原题：https://www.lydsy.com/JudgeOnline/problem.php?id=1098
Offices
Memory limit: 64 MB
Bytel is a mobile telephony potentate. Each employee has been issued a company phone, the memory of which holds the numbers of some of his co-workers (all of them have his number in their phones as well). Due to dynamic growth of their operations the board of directors intends to move company headquaters to new office buildings. It has been decided - in order to boost work efficiency - that every pair of employees working in different buildings should know (reciprocally) each others phone number i.e. the memory of their company phone ought to hold necessary phone numbers.
Simultaneously, the board have decided to rent as many office buildings as possible to ensure good working conditions. Help the board of Bytel to plan the number of office buildings and their size in accordance with the aforementioned requirements.
Task
Write a programme which:
reads the description of employees' phone number lists from the standard input
calculates the maximal number of office buildings and their sizes, satisfying board's conditions
writes the outcome to the standard output.
Input
The first line of the standard input consists of two integers: and (, ), separated by single spaces, denoting the number of Bytel employees and the number of pairs of employees who have their numbers in company phones, respectively. The employees are numbered from to .
Each of the following lines contains a single pair of integers and ( for ), separated by a single space, denoting that employees and have their numbers (reciprocally) in company phones' memory. Each pair of integers denoting a pair of employees shall occur once at the most in the standard input.
Output
The first line of the standard output should contain a single integer: the maximal number of office buildings that Bytel should rent. The second should contain a non-decreasing sequence of positive integers, separated by singe spaces, denoting the sizes of the office buildings (i.e. the numbers of employees working there). Should there exist more than one correct answer - write out any one of them.
Example
For the input data:
7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
the correct result is:
3
1 2 4
An exemplary correct distribution of employees in the office buildings: employee number 4 in the first office, numbers 5 and 7 in the second office, numbers 1, 2, 3, 6 in the third office building.
Task authors: Marek Cygan and Jakub Radoszewski.
题目大意：
给出一张无向图。要求吧这张图拆分为若干块，使得任意两个不在同一个块的点都有边。最大化块的个数。
要求输出块的个数以及每个块的大小。
个人解法：
我这么菜自然不会做。
不过胡思乱想，想到了在反图（据说这个东西又叫补图？）上搞事情。不过由于反图的边数有O(n^2)，不加任何思考就否定了自己的想法。
后来tm正解居然就是反图上搞事情！好气啊。
首先我们发现，满足条件的两个块，在反图上是必然是两个不连通的块。
那么自然问题就转换为了求反图最多可以划分为多少个不连通的块，那相当于求反图上的连通块的个数与大小。
（似乎这个证明很差劲，不如去看看CJ大佬的博客https://blog.csdn.net/z635457712a/article/details/8248364）
然后不会做。就去翻了题解。
算法流程倒是比较简单——还是引用CJ大佬的博客——
那就是我们先把所有的节点挂链，然后再把链表上的一个节点入队，遍历其在原图上相邻的点并做上标记。
那么这时没有打上标记的点在补图上和当前节点一定有边相连因而一定在同一个联通块中，所以再把这些没有打上标记的点入队，并且在链表中除去，继续这个过程，直到队列为空时这个联通块就找出来了。
再取链表上还存在的点入队寻找一个新的联通块，直到删掉所有点为止。
复杂度？
我们发现一个点如果在链表里面被删掉了就不会再遍历了，那么每个点只会入队一次，被删除一次，加上扫描的边。自然复杂度是O(n+m)。
不过没有用链表来做。虽然做的是同样一个事情。
用的是并查集，同样并查集处理这样问题即令Fa[x]为x之后第一个没有被删除的点。作用和链表是一样的。
并查集路径压缩的话，似乎是O(nlogn)的？那么这个算法似乎变为了O(nlogn+m)？反正O(可过)，不太会分析了。脑子短路……
或者引用PoPoQQQ的一个分析https://blog.csdn.net/popoqqq/article/details/44044643：
定义函数Φ为当前未访问过的点数和未访问过的边数之和
初始Φ=n+m，显然任意时刻Φ>=0
每枚举到一个点y，如果x没有向y的边，那么未访问过的点数-1，故Φ会-1
如果x有向y的边，那么未访问过的边数-1，故Φ会-1
因此最终DFS的复杂度为O(n+m)
然后此题就可以A了。似乎跑了5000ms……
代码如下：
https://code.csdn.net/snippets/2197268
后来思考了一下之前一堆并查集的问题为什么不能用链表来做。
大概是因为并查集可以路径压缩，在路径压缩的过程中还可以带权。（链表也可以？）
不过毕竟并查集是O(nlogn)，链表式O(n)啊……
以后做的时候大概需要想一下链表？