并查集是一种数据结构，它跟踪一个集合的元素被分割成若干不相干（不重叠）的子集。union-find算法是一种对这种数据结构执行两种有用操作的算法：
Find：确定一个特定的元素在哪个子集里。这可以用来确定两个元素是否在同一个子集中。
Union：将两个子集连接成一个单一的子集。
在这篇文章中，我们将讨论并查集的应用。这个应用就是检查一个给定的图是否有环。
UnionFInd算法可以检查一个无向图是否有环。注意到我们已经讨论过一种检查环的方法。这是另一种使用并查集的防范。这个方法假设图中没有自环。
我们可以在一个1D数组中跟踪子集，我们称它为parent[]。
我们考虑如下图：
![]()
对于每条边，用边的两个顶点做子集。如果两个顶点都已经在同一个子集中，就发现了一个环。
初始化时，parent的所有槽位都初始化为-1（意味着每个子集中只有一个项目）。
现在逐一处理所有的边。
边0-1：找到顶点0和1所在的子集。由于它们在不同的子集中，我们对它们进行union操作。为了取union，可以让结点0作为节点1的父结点，或者反之。
1
2
| 0 1 2 <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})
1 -1 -1
|
边1-2：1已经在subset 1中，2在subset 2中，所以取union
1
2
| 0 1 2 <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})
1 2 -1
|
边0-2：0在subset 2中，2也在subset 2中。因此，包括这条边形成了一个环。
为什么0的子集和和2相同？
0->1->2 // 1是0的父结点2是1的父结点。
根据以上解释，下面是实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
from collections import defaultdict
class UnionFind:
def __init__(self, k):
self.uf = [-1] * (k + 1)
self.sets_count = k
def find(self, p):
if self.uf[p] < 0:
return p
self.uf[p] = self.find(self.uf[p])
return self.uf[p]
def union(self, p, q):
p_root = self.find(p)
q_root = self.find(q)
if p_root == q_root:
return
if self.uf[p_root] > self.uf[q_root]:
self.uf[q_root] += self.uf[p_root]
self.uf[p_root] = q_root
else:
self.uf[p_root] += self.uf[q_root]
self.uf[q_root] = p_root
self.sets_count -= 1
def is_connected(self, p, q):
return self.find(p) == self.find(q)
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
self.uf = UnionFind(vertices)
def addEdge(self, u, v):
self.graph[u].append(v)
def isCyclic(self):
for i in self.graph:
for j in self.graph[i]:
if self.uf.is_connected(i, j):
return True
self.uf.union(i, j)
def main():
g = Graph(3)
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 0)
print(g.isCyclic())
if __name__ == '__main__':
main()
|
