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

大家好，我是吴师兄，关注我，每周更新大厂最新笔试题解析。

题目描述

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

输入描述

第一行输入一个正整数n，代表节点的数量。

接下来的n-1行，每行输入两个正整数u和v，表示节点u和节点v有一条边链接。

最后一行输出一个正整数x，代表删掉的节点编号。

输出描述

第一行输出一个正整数k，代表连通块的数量。

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

示例一

输入5

1 2

2 3

1 4

1 5

输出3

1 1 2

说明

未删除节点前的树如下图所示。

暂时无法在飞书文档外展示此内容

删除节点后的森林如下图所示，共包含3棵树，大小为1 1 2

暂时无法在飞书文档外展示此内容

示例二

输入7

1 2

3 5

6 8

2 6

4 5

1 5

输出3

1 1 4

解题思路

本题看似要求删除，实际上是需要计算从给定的节点x出发，各个方向上的连通块大小。因此用常规的DFS或BFS就可以完成。

代码

解法一：DFS

# 题目：【DFS&BFS】Shein2023秋招提前批-删点成林# 作者：闭着眼睛学数理化# 算法：DFS# 代码有看不懂的地方请直接在群上提问# DFS递归函数，共包含三个参数：# cur_node：本次DFS搜索中进行到的当前节点# neighbor_table：表示整棵树的邻接表# checkSet：用来判断节点是否已经检查过的集合def dfs(cur_node, neighbor_table, checkSet): # 将本次DFS搜索的连通块大小block_size定义为全局变量 global

block_size

# 当前连通块的大小+1 block_size += 1 # 将当前节点修改为已检查过

checkSet.add(cur_node)

# 遍历当前节点cur_node的所有邻接节点nxt_node for nxt_node in

neighbor_table[cur_node]:

# 如果nxt_node尚未被检查过 if nxt_node not in

checkSet:

# 则可以继续进行DFS搜索

dfs(nxt_node, neighbor_table, checkSet)

from collections import

defaultdict

# 输入节点数目

n = int(input())

# 构建邻接表

neighbor_table = defaultdict(list)

# 对于节点数为n的树，一共有n-1条边，循环n-1次for _ in range(n – 1

# 输入具有连接关系的两个节点a和b

a, b = map(int, input().split())

# a和b具有连接关系，故a的邻接节点中包含b，b的邻接节点包含a

neighbor_table[a].append(b)

neighbor_table[b].append(a)

# 输入删除的节点x

x = int(input())

# 构建答案列表，储存删除x后得到的各个连通块的大小# 即计算以x为起始节点，各个方向上的连通块的大小

ans = list()

# 构建检查集合，储存已经检查过的节点# 由于题目没有说明节点的编号一定是从1到n# 故此处使用哈希集合而不是列表

checkSet = set()

# 将x标记为已检查过

checkSet.add(x)

# 遍历x的所有邻接节点node，从这些邻接节点出发进行DFS搜索for node in

neighbor_table[x]:

# 每一次DFS之前，都要重置本次搜索连通块大小为0 block_size = 0 # 以x的邻接节点node作为DFS的入口，进行DFS函数的递归调用

dfs(node, neighbor_table, checkSet)

# DFS搜索结束，得到连通块的大小block_size，将其加入ans中

ans.append(block_size)

# 输出ans的长度，即为连通块的数目# 实际上连通块的数目也等于x邻接节点的数目，即输出len(neighbor_table[x])也是可以的

print(len(ans))

# 题目要求连通块大小按照升序排序，故此处需要排序后再输出print(” “.join(str(num) for num in

sorted(ans)))

时空复杂度

时间复杂度：O(N)。需要遍历每一个节点。

空间复杂度：O(N)。检查集合checkSet所占空间。

解法二：BFS

# 题目：【DFS&BFS】Shein2023秋招提前批-删点成林# 作者：闭着眼睛学数理化# 算法：BFS# 代码有看不懂的地方请直接在群上提问from collections import

defaultdict, deque

# 输入节点数目

n = int(input())

# 构建邻接表

neighbor_table = defaultdict(list)

# 对于节点数为n的树，一共有n-1条边，循环n-1次for _ in range(n – 1

# 输入具有连接关系的两个节点a和b

a, b = map(int, input().split())

# a和b具有连接关系，故a的邻接节点中包含b，b的邻接节点包含a

neighbor_table[a].append(b)

neighbor_table[b].append(a)

# 输入删除的节点x

x = int(input())

# 构建答案列表，储存删除x后得到的各个连通块的大小# 即计算以x为起始节点，各个方向上的连通块的大小

ans = list()

# 构建检查集合，储存已经检查过的节点# 由于题目没有说明节点的编号一定是从1到n# 故此处使用哈希集合而不是列表

checkSet = set()

# 将x标记为已检查过

checkSet.add(x)

# 遍历x的所有邻接节点node，从这些邻接节点出发进行BFS搜索for node in

neighbor_table[x]:

# 每个邻接节点做一次BFS搜索

q = deque()

q.append(node)

# 将node加入检查集合中

checkSet.add(node)

# 初始化本次BFS搜索的连通块大小为0 block_size = 0 # 进行BFS搜索 while

(len(q)):

# 弹出队头元素，为当前搜索的节点

cur_node = q.popleft()

# 每弹出一个节点，连通块大小+1 block_size += 1 # 遍历当前节点cur_node的所有邻接节点nxt_node for nxt_node in

neighbor_table[cur_node]:

# 如果nxt_node尚未被检查过 if nxt_node not in

checkSet:

# 则将nxt_node加入队列中，等待后续搜索

q.append(nxt_node)

# 同时将nxt_node标记为已检查过

checkSet.add(nxt_node)

# 做完BFS搜索，将本次搜索得到的连通块大小block_size加入ans中

ans.append(block_size)

# 输出ans的长度，即为连通块的数目# 实际上连通块的数目也等于x邻接节点的数目，即输出len(neighbor_table[x])也是可以的

print(len(ans))

# 题目要求连通块大小按照升序排序，故此处需要排序后再输出print(” “.join(str(num) for num in

sorted(ans)))

时空复杂度

时间复杂度：O(N)。需要遍历每一个节点。

空间复杂度：O(N)。检查集合checkSet所占空间。

吴师兄一直在做的一件事

考虑到今年的就业环境，5月份开始，新增了一门课程，想帮助基础不太好但着急找程序员工作的人能先上班养活自己。

短短 3 个月的时间，帮助十来位同学顺利通过机试和拿到 Offer，很多还是零基础那种，说内心话，还是非常有成就感的一件事情。

这个月见证了许多不可能

有一些关注这件事情的朋友问我，自己不想去华为 OD，想去外企或者一些大厂，有没有类似更加符合自己的课程。

问的人多了，也就有了算法训练营的升级版：大厂算法高频题冲刺班。

量大管饱！

这个班着重通过动画的形式讲解大厂真题，直播+视频+文字版解析+答疑讲解，以 acm 的模式进行讲解，多次模拟机试，不怕大厂手撕，同时每一期会迭代15%的真题。

华为校招面试算法真题解析

百度提前批一二三面笔试算法解析

字节抖音电商 java 提前批二面真题解析