108. 冗余连接
-
init
方法重新初始化并查集,使每个节点的父节点指向自己。 -
find
方法实现寻根操作,并应用了路径压缩技术,递归地将直接或间接的父节点指向根节点,优化了查找效率。 -
is_same
方法判断两个节点是否在同一个集合中,通过比较它们的根节点是否相同。 -
join
方法将两个节点加入同一个集合。首先寻找两个节点的根节点,如果根节点相同则直接返回,否则将一个节点的根设置为另一个节点的根。 -
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,