代码随想录算法训练营第五十六天｜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 = n
        self.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 = n
        self.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:
            return
        self.father[root_v] = root_u
 
    def 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)
            return
        uf.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:
            continue
        if uf.same(u, v):
            return False
        uf.join(u, v)
    return True
 
def main():
    n = int(input())
    in_degree = [0] * (n + 1)  # 记录节点入度
    edges = []
    for _ in range(n):
        s, t = map(int,