本次題目都來自卡碼網

108. 冗余連接

無向圖，返回一條可以刪去的邊，使得結果圖是一個有著N個節點的樹（即：只有一個根節點）。

• 從前向后遍歷每一條邊（因為優先讓前面的邊連上），邊的兩個節點如果不在同一個集合，就加入集合（即：同一個根節點）。
• 如果邊的兩個節點已經出現在同一個集合里，說明著邊的兩個節點已經連在一起了，再加入這條邊一定就出現環了。

class UnionFind:def __init__(self, n):self.n = nself.father = [0] * (n + 1)for i in range(n + 1):self.father[i] = idef find(self, u):if u == self.father[u]:return uelse:self.father[u] = self.find(self.father[u])return self.father[u]def join(self, u, v):u = self.find(u)v = self.find(v)if u == v:returnelse:self.father[u] = vdef is_same(self, u, v):u = self.find(u)v = self.find(v)return u == vif __name__ == '__main__':n = int(input())UnionFind = UnionFind(n)for i in range(n):s, t = map(int, input().strip().split())if UnionFind.is_same(s, t):print(str(s) + " " + str(t))exit()else:UnionFind.join(s, t)

109. 冗余連接II

1、先考慮節點有兩個入度的情況，其中必定有一個是冗余的

2、如果不存在1的情況，則考慮環的情況

class UnionFind:def __init__(self, n):self.n = nself.father = [0] * (n + 1)for i in range(n + 1):self.father[i] = idef find(self, u):if u == self.father[u]:return uelse:self.father[u] = self.find(self.father[u])return self.father[u]def join(self, u, v):u = self.find(u)v = self.find(v)if u == v:returnelse:self.father[u] = vdef is_same(self, u, v):u = self.find(u)v = self.find(v)return u == v# 在有向圖里找到刪除的那條邊，使其變成樹
def getRemoveEdge(edges, n):union_find = UnionFind(n)  # 初始化并查集for i in range(union_find.n):  # 遍歷所有的邊if union_find.is_same(edges[i][0], edges[i][1]):  # 構成有向環了，就是要刪除的邊print(str(edges[i][0]) + " " + str(edges[i][1]))else:union_find.join(edges[i][0], edges[i][1])# 刪一條邊之后判斷是不是樹
def isTreeAfterRemoveEdge(edges, deleteEdge, n):union_find = UnionFind(n)  # 初始化并查集for i in range(union_find.n):if i == deleteEdge:continueif union_find.is_same(edges[i][0], edges[i][1]):  # 構成有向環了，一定不是樹return Falseelse:union_find.join(edges[i][0], edges[i][1])return Trueif __name__ == '__main__':n = int(input())edges = []inDegree = [0] * (n + 1)  # 記錄節點入度for i in range(n):s, t = map(int, input().strip().split())inDegree[t] += 1edges.append((s, t))inDegree2 = []  # 記錄入度為2的邊（如果有的話就兩條邊）# 找入度為2的節點所對應的邊，注意要倒序，因為優先刪除最后出現的一條邊for i in range(n - 1, -1, -1):if inDegree[edges[i][1]] == 2:inDegree2.append(i)if len(inDegree2) > 0:# 放在inDegree2里的邊已經按照倒敘放的，所以這里就優先刪inDegree2[0]這條邊if isTreeAfterRemoveEdge(edges, inDegree2[0], n):print(str(edges[inDegree2[0]][0]) + " " + str(edges[inDegree2[0]][1]))else:print(str(edges[inDegree2[1]][0]) + " " + str(edges[inDegree2[1]][1]))exit()# 處理情況三# 明確沒有入度為2的情況，那么一定有有向環，找到構成環的邊返回就可以了getRemoveEdge(edges, n)