0684. Redundant Connection

题目信息

题号:

0684

难度:

Medium

主题:

无向图、树加一条边、环、输入顺序并列规则

原题:

LeetCode 0684

重点:

原图由一棵树额外加入一条无向边得到、删除一条边后需恢复为树、存在多个可删边时返回输入中最后出现者

题目重述

有 n 个编号 1 到 n 的节点。输入 edges 原本来自一棵无向树,但又加入了一条连接两个不同节点、且此前不存在的无向边,因此图中恰好出现一个环。

返回一条边,删除它后图重新成为包含全部节点的树。若环上的多条边都满足条件,返回它们中在 edges 输入顺序里最后出现的那一条。edges.length = n,n 位于 [3, 1000],每条边的两个端点位于 [1, n]。

自建示例

环中最后出现的边优先返回:

输入:edges = [[1,2],[2,4],[4,3],[3,1]]
输出:[3,1]
解释:四条边组成一个环,删除其中任意一条都能得到树;按输入顺序返回环上最后出现的 [3,1]。

额外边连接已有路径两端:

输入:edges = [[1,2],[2,3],[3,5],[3,4],[4,1]]
输出:[4,1]
解释:加入 [4,1] 后形成 1-2-3-4-1 的环,删除该边即可恢复原有树结构。