Union Find Algorithm
Published:
This is my personal notes for Union Find Algorithm.
Introduction
并查集（Union-Find）是解决动态连通性问题的一类非常高效的数据结构，可以用于判断有多少个关系圈，两点是否连通等问题。
可以想象一张地图上有很多点，有些点之间是有道路相互联通的，而有些点则没有。如果我们现在要从点A走向点B，那么一个关键的问题就是判断我们能否从A走到B呢？换句话说，A和B是否是连通的。这是动态连通性最基本的诉求。现在给出一组数据，其中每个元素都是一对“点”，代表这对点之间是联通的，我们需要设计一个算法，让计算机依次读取这些数据，最后判断出其中任意两点是否连通。注意，并查集所涉及的动态连通性只是考虑“是否连通”这一二值判别问题，而不涉及连通的路径到底是什么。
Union
对于每一个关系，我们应用一次联合（Union）操作。一个union操作的流程是这样子的：
对于关系a->b,先通过find找出a和b的祖先parent_a和parent_b,
如果parent_a和parent_b不同，让parent[parent_a] = parent_b
这里只需要修改一个祖先，在a这条路径下的所有节点的祖先都自动被修改为parent_b
Find
找出一个节点祖先的操作find的流程则是：
如果parent[a] = a,返回a
否则返回find(parent[a])
Examples
1 LeetCode Q547 Friend Circles
class Solution:
def findCircleNum(self, M):
N=len(M)
def find(x):
if uf[x]!=x: return find(uf[x])
else: return x
uf=list(range(N))
for i in range(N):
for j in range(N):
if M[i][j]:
uf[find(i)]=find(j)
return len(set(find(i) for i in range(N)))
2 LeetCode Q990 Satisfiability of Equality Equations
import string
class Solution:
def equationsPossible(self, equations):
# 寻找祖先 Find
def find(x):
if uf[x]!=x: return find(uf[x])
else: return x
uf={char:char for char in string.ascii_lowercase}
# 合并祖先 Union
for x,symbol,_,y in equations:
if symbol=='=':
uf[find(x)]=find(y)
return not any(symbol=='!' and find(x)==find(y) for x,symbol,_,y in equations)