{title}

Back to notes

Union-find algorithm

Keywords: algorithms, disjoint set, graphs, undirected graph
Date:
public class UF
  UF(int N)                         // initialize dynamic connectivity structure with N objects
  void union(int p, int q)          // add edge between p and q
  boolean connected(int p, int q)   // check if p and q are within the same component
  • Dynamic connectivity client:
    • Initialize graph with N vertices
    • Loop:
      • for a given unconnected pair of integers, connect them

Code:

public static void main(String[] args)
{
  int N = StdIn.readInt();
  UF uf = new UF(N);
  
  while (!StdIn.isEmpty())
  {
    int p = StdIn.readInt();
    int q = StdIn.readInt();
    
    if (!uf.connected(p, q))
    {
      uf.union(p, q);
      StdOut.println(p + " " + q);
    }
  }
}

Input:

10
4 3
3 8
6 5
9 4
2 1