代码随想录算法训练营第五十六天｜108.冗余连接 、109.冗余连接II

108. 冗余连接

1. init 方法重新初始化并查集，使每个节点的父节点指向自己。

2. find 方法实现寻根操作，并应用了路径压缩技术，递归地将直接或间接的父节点指向根节点，优化了查找效率。

3. is_same 方法判断两个节点是否在同一个集合中，通过比较它们的根节点是否相同。

4. join 方法将两个节点加入同一个集合。首先寻找两个节点的根节点，如果根节点相同则直接返回，否则将一个节点的根设置为另一个节点的根。

5. main 函数读取节点数量 n，初始化并查集，然后循环读取每对节点 s 和 t。如果 s 和 t 在同一个集合中，则打印它们并退出循环；如果不在，则通过 join 方法将它们合并。

class UnionFind:def __init__(self, n):self.n = nself.father = [i for i in range(n+1)]  # 按照节点大小范围定义数组def init(self):# 并查集初始化，每个节点的父节点指向自己self.father = [i for i in range(self.n+1)]def find(self, u):# 并查集里寻根的过程，路径压缩if u != self.father[u]:self.father[u] = self.find(self.father[u])  # 递归地进行路径压缩return self.father[u]def is_same(self, u, v):# 判断 u 和 v 是否找到同一个根return self.find(u) == self.find(v)def join(self, u, v):# 将 v 和 u 合并到同一个集合中root_u = self.find(u)root_v = self.find(v)if root_u == root_v:return  # 如果已经在同一个集合，则直接返回self.father[root_v] = root_u  # 否则，将 v 的根的父节点设置为 u 的根def main():n = int(input())union_find = UnionFind(n)union_find.init()for _ in range(n):s, t = map(int, input().split())if union_find.is_same(s, t):print(s, t)break  # 找到则输出并退出else:union_find.join(s, t)if __name__ == "__main__":main()

109. 冗余连接II

本题的本质是 ：有一个有向图，是由一颗有向树 + 一条有向边组成的 （所以此时这个图就不能称之为有向树），现在让我们找到那条边 把这条边删了，让这个图恢复为有向树。

还有“若有多条边可以删除，请输出标准输入中最后出现的一条边”，这说明在两条边都可以删除的情况下，要删顺序靠后的边！

class UnionFind:def __init__(self, n):self.n = nself.father = [i for i in range(n+1)]  # 按照节点大小范围定义数组def init(self):# 并查集初始化，每个节点的父节点指向自己self.father = [i for i in range(self.n+1)]def find(self, u):# 并查集里寻根的过程，路径压缩if u != self.father[u]:self.father[u] = self.find(self.father[u])return self.father[u]def join(self, u, v):# 将 v 和 u 合并到同一个集合中root_u = self.find(u)root_v = self.find(v)if root_u == root_v:returnself.father[root_v] = root_udef same(self, u, v):# 判断 u 和 v 是否找到同一个根return self.find(u) == self.find(v)def get_remove_edge(uf, edges):uf.init()for u, v in edges:if uf.same(u, v):print(u, v)returnuf.join(u, v)def is_tree_after_remove_edge(uf, edges, delete_edge):uf.init()for i, (u, v) in enumerate(edges):if i == delete_edge:continueif uf.same(u, v):return Falseuf.join(u, v)return Truedef main():n = int(input())in_degree = [0] * (n + 1)  # 记录节点入度edges = []for _ in range(n):s, t = map(int,