0685. Redundant Connection II

题目信息

题号:

0685

难度:

Hard

主题:

有向图、根树、双父节点、环、并列返回规则

原题:

LeetCode 0685

重点:

原结构是有向根树再加入一条边、异常可能表现为节点有两个父亲或形成有向环、删除一条边后必须恢复完整根树

题目重述

有 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。