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 完成