Skip to content

Union-find algorithm

Union-find algorithm

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

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