Union Find (Dynamic Connectivity)

Usage

$ javac UnionFind.java
$ java UnionFind input.txt

Feature

• union: connect two objects
• connected: is there a path conneting the two objects
• connected component: maximal set of objects that are mutuall connected, any two objects in them are connected

Term

• reflexive: p > p
• symmetric: p > q -> q > p
• transitive p > q, q > r -> p > r