Quick Find Algorithm

This algorithm can be used to solve dynamic connectivity problem. This algorithm is kept very simple. It supports two operations,

·         connected(a, b) check if a and b are in the same component

·         union(a, b) if two elements are not in the same component then this operation merge these components(merge(component of a, component of b))

Data-Structure

This algorithm uses a simple array id[] to maintain each element's component.

Dynamic Connectivity Problem

Problem specification: The input is a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p q as meaning “p is connected to q.” We assume that “is connected to” is an   equivalence relation, which means that it is

■  Reflexive  : p is connected to p.

■  Symmetric  : If p is connected to q, then q is connected to p.

■  Transitive : If p is connected to q and q is connected to r, then p is connected to r.