#CF920E. Connected Components?

Connected Components?

好的,这是您要求的算法题题面的中文翻译和排版:


E. 连通分量?

每个测试点的时间限制:22
每个测试点的内存限制:256256 MB
输入:标准输入
输出:标准输出

给定一个包含 nn 个顶点和若干条边的无向图。与通常直接给出图中存在的边不同,本题会给出 mm 个无序对 (x,y)(x, y),表示顶点 xxyy 之间没有边。如果某对顶点没有在输入中列出,则这两个顶点之间存在一条边。

你需要找出该图中的连通分量个数,以及每个连通分量的大小。一个连通分量是指顶点集合 XX,满足对于该集合中的任意两个顶点,图中至少存在一条路径连接它们,但如果将任何其他顶点加入 XX,这一性质就会被破坏。

输入

第一行包含两个整数 nnmm1n2000001 \le n \le 2000000mmin(200000,n(n1)2)0 \le m \le \min(200000, \frac{n(n-1)}{2}))。

接下来 mm 行,每行包含两个整数 xxyy1x,yn1 \le x, y \le nxyx \ne y),表示顶点 xxyy 之间没有边。每对顶点最多出现一次;(x,y)(x, y)(y,x)(y, x) 被视为相同(因此它们不会在同一个测试用例中同时出现)。如果某对顶点没有在输入中列出,则这两个顶点之间存在一条边。

输出

首先输出一个整数 kk —— 图中连通分量的个数。

然后输出 kk 个整数 —— 每个连通分量的大小。这些整数应按非递减顺序输出。

输入示例

5 5
1 2
3 4
3 2
4 2
2 5

输出示例

2
1 4