0684. Redundant Connection¶
题目信息¶
- 题号:
0684
- 难度:
Medium
- 主题:
无向图、树加一条边、环、输入顺序并列规则
- 原题:
- 重点:
原图由一棵树额外加入一条无向边得到、删除一条边后需恢复为树、存在多个可删边时返回输入中最后出现者
题目重述¶
有 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 的环,删除该边即可恢复原有树结构。