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
123
124
125
126
127
// @Title: 冗余连接 II (Redundant Connection II)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 8 ms
// @Memory: 3.5 MB
/*
 * @lc app=leetcode.cn id=685 lang=golang
 *
 * [685] 冗余连接 II
 *
 * https://leetcode-cn.com/problems/redundant-connection-ii/description/
 *
 * algorithms
 * Hard (30.07%)
 * Likes:    26
 * Dislikes: 0
 * Total Accepted:    660
 * Total Submissions: 2.2K
 * Testcase Example:  '[[1,2],[1,3],[2,3]]'
 *
 * 在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。
 * 
 * 输入一个有向图,该图由一个有着N个节点 (节点值不重复1, 2, ..., N)
 * 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。
 * 
 * 结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v],用以表示有向图中连接顶点 u and
 * v和顶点的边,其中父节点u是子节点v的一个父节点。
 * 
 * 返回一条能删除的边,使得剩下的图是有N个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
 * 
 * 示例 1:
 * 
 * 
 * 输入: [[1,2], [1,3], [2,3]]
 * 输出: [2,3]
 * 解释: 给定的有向图如下:
 * ⁠ 1
 * ⁠/ \
 * v   v
 * 2-->3
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
 * 输出: [4,1]
 * 解释: 给定的有向图如下:
 * 5 <- 1 -> 2
 * ⁠    ^    |
 * ⁠    |    v
 * ⁠    4 <- 3
 * 
 * 
 * 注意:
 * 
 * 
 * 二维数组大小的在3到1000范围内。
 * 二维数组中的每个整数在1到N之间,其中 N 是二维数组的大小。
 * 
 * 
 */

 func findRedundantDirectedConnection(edges [][]int) []int {
	n := len(edges)

	parent := make([]int, n+1)
	var first, last []int

	// 1. 判断是否有两个父节点的情况
	for k := range edges {
		p, c := edges[k][0], edges[k][1]
		if parent[c] == 0 {
			parent[c] = p
		} else {
			// c是存在两个父节点的节点
			first = []int{parent[c],c}
			last = edges[k]

			edges[k] = nil
			break
		}
	}

	root := parent
	for i :=0; i<=n;i++ {
		root[i] = i
	}

	rootOf := func(i int) int {
		for i != root[i] {
			// 为什么在这里直接return root[i], 答案会不一致? -> 因为直接return, 并没有改变root[i]的值
			// return root[i]
			i = root[i]
		}
		return i
	}

	// 2. 判断有没有环的情况
	for _, edge := range edges {
		if edge == nil {
			continue
		}

		p := edge[0]
		c := edge[1]
		r := rootOf(p)

		if r == c {
			// 3. 不存在有两个父节点的节点
			// 返回让环封闭的 edge
			if first == nil {
				return edge
			}
			return first
		}

		root[c] = r
	}

	// 4. 不存在上述3种情况, 返回一条能删除的边
	return last

}