1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// @Title: 冗余连接 (Redundant Connection)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 8 ms
// @Memory: 3.1 MB
/*
 * @lc app=leetcode.cn id=684 lang=golang
 *
 * [684] 冗余连接
 *
 * https://leetcode-cn.com/problems/redundant-connection/description/
 *
 * algorithms
 * Medium (53.11%)
 * Likes:    50
 * Dislikes: 0
 * Total Accepted:    2.8K
 * Total Submissions: 5.2K
 * Testcase Example:  '[[1,2],[1,3],[2,3]]'
 *
 * 在本问题中, 树指的是一个连通且无环的无向图。
 *
 * 输入一个图,该图由一个有着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。对于造成任何不便,我们深感歉意。
 *
 */
func findRedundantConnection(edges [][]int) []int {
	if len(edges) == 0 {
		return []int{}
	}
	p := make([]int, len(edges)+1)

	for i := 1; i < len(edges)+1; i++ {
		p[i] = i
	}

	for i := 0; i < len(edges); i++ {
		u := edges[i][0] //1
		v := edges[i][1] //2

		// 妙啊!!!
		for u != p[u] {
			u = p[u]
		}
		for v != p[v] {
			v = p[v]
		}

		if u == v {
			return []int{edges[i][0], edges[i][1]}
		}
		p[u] = p[v]
	}

	return []int{}
}

/*
func findRedundantConnection(edges [][]int) []int {
	n := len(edges)
	parent := make([]int, n+1)
	for i := range edges {
		parent[i] = i
	}

	for i, e := range edges {
		f, t  := e[0], e[1]
		pf := find(parent, f)
		pt := find(parent, t)
		if pf == pt {
			return edges[i]
		}
		parent[pf] = pt
	}

	return  edges[n-1]
}

// 使用并查集
func find(parent []int, f int) int {
	for f != parent[f] {
		f = parent[f]
	}
	return f
}
*/