在本问题中, 树指的是一个连通且无环的无向图。
输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点u 和v的无向图的边。
返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
示例 1:
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \\
2 - 3
示例 2:
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
注意:
输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间,其中N是输入数组的大小。
更新(2017-09-26):
我们已经重新检查了问题描述及测试用例,明确图是无向 图。对于有向图详见冗余连接II。对于造成任何不便,我们深感歉意。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/redundant-connection
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:标准的并差集模板即可解决
```python
#
# @lc app=leetcode id=684 lang=python3
#
# [684] Redundant Connection
#
# @lc code=start
class Solution:
def unionFind(self, root, v1, v2):
while (root[v1] != v1):
v1 = root[v1]
while (root[v2] != v2):
v2 = root[v2]
if (root[v1] != root[v2]):
root[v2] = v1
if (v1!= v2):
return False
return True
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
m = len(edges)
root = [0] * 2000
for i in range(m):
root[i] = i
for i in range(m):
v1 = edges[i][0]
v2 = edges[i][1]
edge = self.unionFind(root, v1, v2)
if (edge):
return [v1, v2]
return []
# @lc code=end
```
可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解黑白圆盘一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可
LeetCode题解圆上任取三点构成锐角三角形的概率来自字节跳动的一道几何题题解:1/4
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈