108. 冗余连接
本题光看题目没理解具体什么意思；看了题解有点明白了；（个人觉得还是力扣的题目描述比较容易理解）
题目意思：大概就是加一条边使树结构有环，然后再环中去掉一条边（如果环中多条边可取，则去掉最后一条边），仍然变成一颗树结构；
思路：观察两个节点是否再一个集合，如果不在，也可以将两个节点添加到一个集合中；
class UnionFind:
def __init__(self, size):
self.parent = list(range(size + 1)) # 初始化并查集
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u]) # 路径压缩
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
self.parent[root_v] = root_u
def is_same(self, u, v):
return self.find(u) == self.find(v)
def main():
# 输入
n = int(input())
uf = UnionFind(n)
# 寻找冗余边
res = None
for i in range(n):
s, t = map(int, input().split())
if uf.is_same(s, t):
res = str(s) + ' ' + str(t)
else:
uf.union(s, t)
# 输出
print(res)
if __name__ == '__main__':
main()109. 冗余连接II
本题与KM108.冗余连接类似，但本题是一个有向图，有向图相对要复杂一些；
如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）；
所以情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了；
情况二： 入度为2 的一种情况下只能删特定的一条边，如下图所示；该情况只能删除这条边（节点1 -> 节点3）
情况三： 如果没有入度为2的点，说明 图中有环了（注意是有向环），对于这种情况，删除构成环的边就可以了；
from collections import defaultdict
class UnionFind:
def __init__(self, size):
self.parent = list(range(size + 1)) # 初始化并查集
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u]) # 路径压缩
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
self.parent[root_v] = root_u
def is_same(self, u, v):
return self.find(u) == self.find(v)
def is_tree_after_remove_edge(self, edges, edge, n):
for i in range(len(edges)):
if i == edge:
continue
s, t = edges[i]
if self.is_same(s, t): # 成環，即不是有向樹
return False
else: # 將s,t放入集合中
self.union(s, t)
return True
def get_remove_edge(self, edges):
for s, t in edges:
if self.is_same(s, t):
print(s, t)
return
else:
self.union(s, t)
def main():
# 输入
n = int(input())
edges = list()
in_degree = defaultdict(int)
uf = UnionFind(n)
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 uf.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:
# 情況三：有环
uf.get_remove_edge(edges)
if __name__ == '__main__':
main()