- 遍历问题
这道题的 DFS/BFS 题怎么做?
- @ 2026-8-14 22:18:54
题目是:给一棵有根树,可以删掉一些子树,让剩下的树(整体)DFS序 = BFS序。要删最少结点,还要输出剩下树的 DFS 序。
我自己推出来几个点:
样例 n=6, 边: 1-2,1-3,2-4,4-5,4-6,答案是最少删 1 个(删 3),剩下树 DFS 和 BFS 都是 1 2 4 5 6。
我一开始觉得 DFS序 = BFS序 等价于树是一条链,但这里 4 有 5、6 两个儿子,树不是链,序列却一样。所以这个结论不对。
我试过只保留根到每个叶子的最长链,算出来是 2,但正确答案是 1,所以也不是简单地只保留一条链。
输出格式写的是两行:第一行是删点数,第二行是剩下连通块的 DFS 序列。但样例输出只有一行 1,第二行为空?还是说剩下只有一个连通块所以第二行可以不输出?
现在卡住了,想问:
DFS序 = BFS序 的充要条件到底是什么?
最少删点的贪心/DP 应该怎么做?
第二行要输出的 DFS 序列,是删完之后剩下树的 DFS 序吗?多个连通块怎么处理?
如果有大佬懂这题,麻烦讲讲思路,感谢!
1 条评论
-
AbCDeFG @ 2026-8-16 18:22:17已修改
DFS 是什么?
我问了豆包,他说你的样例根不确定,所以不能找到答案
- 1
信息
- ID
- 147
- 时间
- ms
- 内存
- MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 4
- 已通过
- 1
- 上传者