代码随想录算法训练营 Day 48
Published:
并查集
并查集常用来解决连通性问题，主要的两个功能：1. 将两个元素添加到一个集合中；2. 判断两个元素在不在同一个集合中
Q1. KamaCoder 108
当两个节点的根节点一致时，说明他们之间已经有一条路径。如果此时再加上一条边直接连接这两个节点，就会形成环。因此我们首先判断要插入边的两个节点是否有同一个根节点，没有的话通过并查集将其加入到同一个集合中
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
def find(self, u):
if u != self.parent[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)
if __name__ == '__main__':
n = int(input())
uf = UnionFind(n)
for _ in range(n):
s, t = map(int, input().split())
if uf.is_same(s, t):
print(s, t)
exit()
uf.union(s, t)
Q2. KamaCoder 109
有向图要构成树有两个条件：1. 除根节点外，每个节点入度必须为1；2. 不可以形成有向环
具体的步骤：1. 是否有造成入度为2的边；2. 如果有的话，逐一判断不包括一条边时，能够形成树，如果可以的话说明这条边就是要删除的边；3. 如果没有入度为2的节点，说明此时存在有向环，删除环中一条边即可
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
def find(self, u):
if u != self.parent[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 find_cycle(size, edges):
uf = UnionFind(size)
for x, y in edges:
if uf.is_same(x, y):
return x, y
uf.union(x, y)
return None
def is_tree_after_remove(size, e, edges):
uf = UnionFind(size)
for x, y in edges:
if x == e[0] and y == e[1]:
continue
if uf.is_same(x, y):
return False
uf.union(x, y)
return True
if __name__ == '__main__':
n = int(input())
in_degree = [0] * (n + 1)
edges = []
for _ in range(n):
s, t = map(int, input().split())
in_degree[t] += 1
edges.append((s, t))
edge = []
for i in range(n - 1, -1, -1):
if in_degree[edges[i][1]] == 2:
edge.append(edges[i])
if edge:
for e in edge:
if is_tree_after_remove(n, e, edges):
print(e[0], e[1])
exit()
else:
x, y = find_cycle(n, edges)
print(x, y)