0684. Redundant Connection ========================== 题目信息 -------- :题号: 0684 :难度: Medium :主题: 无向图、树加一条边、环、输入顺序并列规则 :原题: `LeetCode 0684 `_ :重点: 原图由一棵树额外加入一条无向边得到、删除一条边后需恢复为树、存在多个可删边时返回输入中最后出现者 题目重述 -------- 有 ``n`` 个编号 ``1`` 到 ``n`` 的节点。输入 ``edges`` 原本来自一棵无向树,但又加入了一条连接两个不同节点、且此前不存在的无向边,因此图中恰好出现一个环。 返回一条边,删除它后图重新成为包含全部节点的树。若环上的多条边都满足条件,返回它们中在 ``edges`` 输入顺序里最后出现的那一条。``edges.length = n``,``n`` 位于 ``[3, 1000]``,每条边的两个端点位于 ``[1, n]``。 自建示例 -------- 环中最后出现的边优先返回: .. code-block:: text 输入:edges = [[1,2],[2,4],[4,3],[3,1]] 输出:[3,1] 解释:四条边组成一个环,删除其中任意一条都能得到树;按输入顺序返回环上最后出现的 [3,1]。 额外边连接已有路径两端: .. code-block:: text 输入:edges = [[1,2],[2,3],[3,5],[3,4],[4,1]] 输出:[4,1] 解释:加入 [4,1] 后形成 1-2-3-4-1 的环,删除该边即可恢复原有树结构。