算法训练营day56 图论⑥ 108. 109.冗余连接系列

        仍然是并查集的练习

108.冗余连接系列

        这是一道典型的并查集问题，并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。

        理解题意，转化问题，把题中所给的边逐个相连，如果在尝试连接的时候出现了需要连接的两个边在集合中出现过，则为冗余边（简单理解就是无向图，不能出现环）

        增加对于join函数的理解，连接之后必定在一个集合中，同一个集合中元素的根必定相同

father = list()def find(u):if u == father[u]:return uelse:father[u] = find(father[u])return father[u]def is_same(u, v):u = find(u)v = find(v)return u == vdef join(u, v):u = find(u)v = find(v)if u != v:father[u] = vif __name__ == "__main__":# 輸入n = int(input())for i in range(n + 1):father.append(i)# 尋找冗余邊    result = Nonefor i in range(n):s, t = map(int, input().split())if is_same(s, t):result = str(s) + ' ' + str(t)else:join(s, t)# 輸出print(result)

109.冗余连接系列②

        本题相对较难

        这道题的本质是：删除“环”，但是有向图中的“环”，不仅仅是“顺序联通的”，还有“非顺序联通的”

        题目规定：有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1

• 情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。选择删顺序靠后便可。
• 情况二：入度为2 还有一种情况——只能删特定的一条边，综上，如果发现入度为2的节点，我们需要判断 删除哪一条边，如果是删哪个都可以，优先删顺序靠后的边。
• 情况三： 如果没有入度为2的点，说明 图中有环了（注意是有向环），和上题思路一致

from collections import defaultdict# 全局变量，用于存储每个节点的父节点，实现并查集数据结构
father = list()def find(u):"""查找节点u的根节点，同时进行路径压缩优化路径压缩可以加快后续的查询速度"""if u == father[u]:# 如果u是自身的父节点，说明u是根节点return uelse:# 递归查找父节点的根节点，并将u的父节点直接指向根节点（路径压缩）father[u] = find(father[u])return father[u]def is_same(u, v):"""判断两个节点是否属于同一个集合（是否具有相同的根节点）"""u = find(u)v = find(v)return u == vdef join(u, v):"""将两个节点所在的集合合并"""u = find(u)v = find(v)if u != v:# 如果根节点不同，则将其中一个根节点的父节点指向另一个根节点father[u] = vdef is_tree_after_remove_edge(edges, edge, n):"""判断移除指定边后，剩余的边是否能构成一棵树edges: 所有边的列表edge: 要移除的边的索引n: 节点总数"""# 声明使用全局变量fatherglobal father # 初始化并查集，每个节点的父节点初始化为自身father = [i for i in range(n + 1)]for i in range(len(edges)):# 跳过要移除的边if i == edge:continues, t = edges[i]if is_same(s, t):# 如果两个节点已经在同一集合中，添加这条边会形成环，不能构成树return Falseelse:# 将两个节点合并到同一集合join(s, t)# 所有边处理完毕后没有形成环，说明可以构成树return Truedef get_remove_edge(edges):"""当图中存在环但没有入度为2的节点时，找到构成环的边并返回此时删除环中的任意一条边都可使图成为树"""# 声明使用全局变量fatherglobal father# 初始化并查集father = [i for i in range(n + 1)]for s, t in edges:if is_same(s, t):# 找到构成环的边，直接输出并返回print(s, t)returnelse:# 合并两个节点join(s, t)if __name__ == "__main__":# 读取节点数量n = int(input())edges = list()# 用于记录每个节点的入度in_degree = defaultdict(int)# 读取所有边并记录入度for i in range(n):s, t = map(int, input().split())in_degree[t] += 1  # 目标节点t的入度加1edges.append([s, t])# 寻找入度为2的节点对应的边，并记录这些边的索引vec = list()# 从后往前遍历，确保后续判断时优先考虑靠后的边for i in range(n - 1, -1, -1):if in_degree[edges[i][1]] == 2:vec.append(i)# 根据不同情况输出结果if len(vec) == 2:# 情况一：存在入度为2的节点，尝试删除输出顺序靠后的边if is_tree_after_remove_edge(edges, vec[0], n):print(edges[vec[0]][0], edges[vec[0]][1])# 情况二：删除第一条边不行，只能删除另一条导致入度为2的边else:print(edges[vec[1]][0], edges[vec[1]][1])else:# 情况三：不存在入度为2的节点，说明原图有环，找到构成环的边并删除get_remove_edge(edges)