AlgoMooc
← 返回题库

P6000. 删点成林

中等通过率 42% · 提交 19 · 通过 8
DFSBFS图论DFS/BFS

一个人拿了一棵树,准备去掉这树上的一个节点(同时把该节点的边都删除),于是形成了一个森林。要求输出该森林的连通块数量,以及每个连通块的大小(按大小的升序输出)

输入描述

第一行输入一个正整数n,代表节点的数量。 接下来的n-1行,每行输入两个正整数u和v,表示节点u和节点v有一条边链接。 最后一行输出一个正整数x,代表删掉的节点编号。

输出描述

第一行输出一个正整数k,代表连通块的数量。 第二行升序输出k个正整数a_i,代表每个连通块的大小。

示例

示例 1

输入

5
1 2
2 3
1 4
1 5
1

输出

3 
1 1 2

时间限制 1000 ms · 内存限制 128 MB

写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「删点成林」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。