A5413 | $Connected Components?$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个包含 $n$ 个顶点和 $\binom{n}{2}$ 条边的无向图。不同于直接给出图中存在的边，本题给出 $m$ 个无序对 $(x, y)$，表示在 $x$ 和 $y$ 之间没有边连接。如果输入中没有出现的任意一对顶点之间都存在一条边。 你需要求出图中连通块的数量以及每个连通块的大小。连通块是指这样一个顶点集合 $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)$ 视为相同的对（同一测试中不会重复出现）。如果某对顶点未在输入中出现，表示它们之间存在一条边。

首先输出 $k$，表示该图中连通块的数量。 然后输出 $k$ 个整数，表示每个连通块的大小。请按非递减顺序输出这些整数。

输入 #1

输出 #1

2
1 4

C++ 编辑器

输入

输出