A5413. Connected Components?
编程题
普及/提高-
知识点
题目描述
给定一个包含 $n$ 个顶点和 $\binom{n}{2}$ 条边的无向图。不同于直接给出图中存在的边，本题给出 $m$ 个无序对 $(x, y)$，表示在 $x$ 和 $y$ 之间没有边连接。如果输入中没有出现的任意一对顶点之间都存在一条边。
你需要求出图中连通块的数量以及每个连通块的大小。连通块是指这样一个顶点集合 $X$，满足集合中任何两点之间至少有一条路径相连，但如果将其他顶点加入集合 $X$，就不再满足这个条件。
你需要求出图中连通块的数量以及每个连通块的大小。连通块是指这样一个顶点集合 $X$，满足集合中任何两点之间至少有一条路径相连，但如果将其他顶点加入集合 $X$，就不再满足这个条件。
输入格式
第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 200000$，$0 \leq m \leq 500000$）。
接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$，$x \neq y$），表示在 $x$ 和 $y$ 之间没有边连接。每对无序对最多出现一次；$(x, y)$ 和 $(y, x)$ 视为相同的对（同一测试中不会重复出现）。如果某对顶点未在输入中出现，表示它们之间存在一条边。
接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$，$x \neq y$），表示在 $x$ 和 $y$ 之间没有边连接。每对无序对最多出现一次；$(x, y)$ 和 $(y, x)$ 视为相同的对（同一测试中不会重复出现）。如果某对顶点未在输入中出现，表示它们之间存在一条边。
输出格式
首先输出 $k$，表示该图中连通块的数量。
然后输出 $k$ 个整数，表示每个连通块的大小。请按非递减顺序输出这些整数。
然后输出 $k$ 个整数，表示每个连通块的大小。请按非递减顺序输出这些整数。
输入输出样例
输入 #1
5 5 1 2 3 4 3 2 4 2 2 5
输出 #1
2 1 4