更弱智的算法学习 day56

使用并查集遍历所有边。当遇到一条边连接的两个节点已经属于同一连通分量时，这条边就是冗余边（因为它会形成环）。由于代码按输入顺序遍历边，最后记录的冗余边即为输入中最后出现的。

• 遍历每条边时，若s和t已连通（is_same(s, t)为True），说明添加该边会形成环，因此记录为result。由于继续遍历后续边，result会被更新，最终保留的是最后一条导致环的边，符合题目要求。若非冗余边，则调用join(s, t)合并集合，维护连通性。

• ​输出​：打印最后记录的冗余边。

father = list() def find(u): if u == father[u]: return u else: father[u] = find(father[u]) return father[u] def is_same(u, v): u = find(u) v = find(v) return u == v def join(u, v): u = find(u) v = find(v) if u != v: father[u] = v if __name__ == "__main__": # 輸入 n = int(input()) for i in range(n + 1): father.append(i) # 尋找冗余邊 result = None for 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)

from collections import defaultdict father = list() def find(u): if u == father[u]: return u else: father[u] = find(father[u]) return father[u] def is_same(u, v): u = find(u) v = find(v) return u == v def join(u, v): u = find(u) v = find(v) if u != v: father[u] = v def is_tree_after_remove_edge(edges, edge, n): # 初始化并查集 global father father = [i for i in range(n + 1)] for i in range(len(edges)): if i == edge: continue s, t = edges[i] if is_same(s, t): # 成環，即不是有向樹 return False else: # 將s,t放入集合中 join(s, t) return True def get_remove_edge(edges): # 初始化并查集 global father father = [i for i in range(n + 1)] for s, t in edges: if is_same(s, t): print(s, t) return else: 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 edges.append([s, t]) # 尋找入度為2的邊，並紀錄其下標(index) vec = list() for i in range(n - 1, -1, -1): if in_degree[edges[i][1]] == 2: vec.append(i) # 輸出 if len(vec) > 0: # 情況一：刪除輸出順序靠後的邊 if is_tree_after_remove_edge(edges, vec[0], n): print(edges[vec[0]][0], edges[vec[0]][1]) # 情況二：只能刪除特定的邊 else: print(edges[vec[1]][0], edges[vec[1]][1]) else: # 情況三： 原圖有環 get_remove_edge(edges)