LeetCode题解684. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图,该图由一个有着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题解黑白圆盘

一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可

LeetCode题解圆上任取三点构成锐角三角形的概率

来自字节跳动的一道几何题题解:1/4

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈