Union Find

Method

A data structure that keeps track of a set of elements partitioned into a number of disjoint (non- overlapping) subsets.

每个集合由一个根节点表示.

有两种基本操作: union(e1, e2)和find(e). 前者把两个e1和e2所代表的集合合并成一个集合. find(e)给出包含该元素的集合的根节点.

实现核心是每个元素记录下它的父节点. find时就顺着它的父节点一直往上遍历下去即可(用递归).

union和find的时间复杂度都是O(N).

find操作可以作path compression, 即顺着父亲往上遍历时把所有遍历到的节点的father都设成根. 时间复杂度会降低些.

还可以配合dummy node, 快速检查是否和某些特定点相连.

Application

1. 数有几个相连的.