P12451 [INOI Team Selection 2021] Labelless Graph

题目描述

某天 Shayan 有一个包含 $n$ 个顶点的图,顶点原本用数字 $1$ 到 $n$ 标号,但这个图被人偷走了。 小偷给 Shayan 发送了 $n$ 张这个图的照片,每张照片中恰好删除了一个顶点,其余顶点的标号被重新编号为 $1$ 到 $n-1$(每个顶点恰好在一张图中被删除)。 小偷告诉他,如果能说出原图中连通分量的大小,他们就会把图还给他。但遗憾的是 Shayan 不记得这个问题的答案,所以他请你帮忙找出答案。

输入格式

第一行包含整数 $n$,表示原图的顶点数量。 接下来的 $n$ 组数据描述 $n$ 张照片。第 $i$ 张图的第一行是 $m_i$,表示删除某个特定顶点后图中边的数量。顶点被随机打乱,标号为 $1$ 到 $n-1$。接下来的 $m_i$ 行描述图中的边。 保证输入数据不会自相矛盾。

输出格式

第一行输出原图的连通分量数量。第二行按非递减顺序输出各连通分量的大小。

说明/提示

### 样例解释 2 在第二个样例中,原图有两个连通分量,其中一个是一条单独的边,另一个是 $P_3$(即包含 3 个顶点的路径图)。 ### 数据范围 - $2 \leq n \leq 300$ - $0 \leq m_i \leq \binom{n-1}{2}$ - $1 \leq v_i, u_i \leq n - 1$ ### 子任务 | 子任务 | 分值 | 限制条件 | |:-------:|:-----:|:---------:| | 1 | 100 | 无额外限制 | 翻译由 DeepSeek V3 完成