LeetCode - 685. 冗余连接 II

. - 力扣（LeetCode）

题目

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。每个元素是一对 [ui, vi]，用以表示有向图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

错误尝试

这是LeetCode-684. 冗余连接-CSDN博客的一个延伸题，首先我尝试了一下直接用基础的差并集方法是否可解：

class Solution:def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:n = len(edges)# 定义关系集合relataions = [[i] for i in range(1, n+1)]for edge in edges:node_0 = edge[0]node_1 = edge[1]# 逐条更新关系集合if relataions[node_0 - 1] != relataions[node_1 - 1]:index = min(relataions[node_0 - 1], relataions[node_1 - 1])max_index = max(relataions[node_0 - 1], relataions[node_1 - 1])relataions = [index if i == max_index else i for i in relataions ]else:return edge  # 返回多余边return []

提交后报错：

分析出错原因：

解题过程如下图所示。

[2, 1] 和 [1, 4] 是环里面的两条边，去掉任意一条环都可以解开，对于无向树固然成立。

但是题目中的树是有向的，只能去掉[2, 1]，才能形成一条正确的树。

正确解题思路：

基于并查集的解法

根据题目描述，这是一棵只有一条附加边的有向树，
- 根据树的性质，节点数量 = 边的数量 + 1，所以这棵多了一条附加边的有向树，节点的数量 = 边的数量
- 环的性质：环上的任意两个节点可以找到一个共同的子节点。
- 根据树的性质，根节点入度为0，其余节点入度为1。添加一条附加边后会出现什么现象呢？
  - 情况1：如果附加边指向根节点，则所有节点入度为1（即所有节点都只有1个父节点），此时一定存在环，即存在1条环路边（即加入后使图中出现环路的边），此时删除环路边即可。
  - 如果附加边不指向根节点，则存在一个子节点入度为2（存在1个节点，有2个父节点），
    - 情况2：此时可能不存在环（如第二个图）：那么此时只有1条冲突边（即与其他边指向同一个子节点的边），此时删除冲突边即可。
    - 情况3：也可能存在环（如第三个图）：此时存在1条冲突边和1条环路边，此时删除导致环路的冲突边。

接下来完成代码：

class Solution:def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:n = len(edges)parents = list(range(n + 1)) # 记录每个节点的父节点child = list(range(n + 1))def find(index: int) -> int:"""返回当前节点对应的最新子节点同时把路径上所有节点都更新最指向最新子节点"""if child[index] != index:child[index] = find(child[index]) # 更新所有child为最新childreturn child[index] # 返回最后一条边加入后的子节点def union(node_0: int, node_1: int):child[find(node_0)] = find(node_1)conflict = -1 cycle = -1for index, (node_0, node_1) in enumerate(edges):if parents[node_1] != node_1:# 初始状态下node的父节点是自身；# 此时node_1 已经有父节点，因此出现冲突conflict = indexelse:parents[node_1] = node_0 # 更新父节点记录if find(node_0) == find(node_1):# 出现环路cycle = indexelse:union(node_0, node_1)if conflict < 0:# 根据前面分析的三种情况，如果无冲突，则一定有环路return edges[cycle]elif cycle < 0:# 根据前面分析的三种情况，如果无环路，则一定有冲突return edges[conflict]else:# 同时有环路和冲突，删除导致环路的冲突边return [parents[edges[conflict][1]], edges[conflict][1]]