0685. Redundant Connection II¶
题目信息¶
- 题号:
0685
- 难度:
Hard
- 主题:
有向图、根树、双父节点、环、并列返回规则
- 原题:
- 重点:
原结构是有向根树再加入一条边、异常可能表现为节点有两个父亲或形成有向环、删除一条边后必须恢复完整根树
题目重述¶
有 n 个编号 1 到 n 的节点。输入 edges 原本来自一棵有向根树:除根节点外每个节点恰有一个父节点,并且从根可到达全部节点;随后又加入了一条此前不存在的有向边。
返回一条需要删除的边,使剩余边重新组成包含全部节点的有向根树。若有多个删除方案,返回其中在输入数组中最后出现的边。edges.length = n,n 位于 [3, 1000],每条边 [u,v] 表示从父候选节点 u 指向子候选节点 v。
自建示例¶
一个节点收到两个父边:
输入:edges = [[1,2],[1,3],[2,3]]
输出:[2,3]
解释:节点 3 同时收到来自 1 和 2 的边;删除后出现的 [2,3] 后,1 成为根且可到达其余节点。
额外边形成有向环:
输入:edges = [[1,2],[2,3],[3,1],[3,4]]
输出:[3,1]
解释:前三条边形成有向环,删除 [3,1] 后得到以 1 为根的有向树,并保留节点 4。