Shein 2023 秋招提前批-删点成林

文章预览

来自公众号： 吴师兄学算法 题目描述 一个人拿了一棵树，准备去掉这树上的一个节点（同时把该节点的边都删除)，于是形成了一个森林。要求输出该森林的连通块数量，以及每个连通块的大小（按大小的升序输出） 输入描述 第一行输入一个正整数 n ，代表节点的数量。 接下来的 n-1 行，每行输入两个正整数 u 和 v ，表示节点 u 和节点 v 有一条边链接。 最后一行输出一个正整数 x ，代表删掉的节点编号。 输出描述 第一行输出一个正整数 k ，代表连通块的数量。 第二行升序输出 k 个正整数 a_i ，代表每个连通块的大小。 示例一 输入 5 1 2 2 3 1 4 1 5 1 输出 3 1 1 2 说明 未删除节点前的树如下图所示。 暂时无法在飞书文档外展示此内容 删除节点后的森林如下图所示，共包含 3 棵树，大小为 1 1 2 暂时无法在飞书文档外展示此内容 示例二 输入 7 1 2 3 5 6 ………………………………