Union Find

What you will learn in this section:

Union Find

Union Find is the approach of constructing graphs. The word union implies already what the algorithm does; creating a union, finding a union between vertices. The only data structure you need is a simple array. Now to the one million dollar question....What do we need it for? It is a basic approach for quickly finding out how many connected components the whole graph has. It's basically being used for a disjoint set of vertices. When I started studying computer science, I always thought, I would not really need union find. The more I got into this topic, I have realized how simple it is. You can fastly determine wether your whole graph is connected, if it has cycles without implementing all kinds of data structures. It is pretty easy using DFS/BFS with importing libraries but implementing it all by yourself is a lot of work, while you can do it in 5 minutes with union find and an array.
As usual, there are a couple of implementations with different runtimes. We are going to learn quick find, quick union, path compression and union rankings.


Your first step would always be to create an array with the size of the amount of vertices. We call this array root, because this particular vertex in the index of your array is connected to another vertex, or in the beginning, with itself. That is why we initialise every index with the vertex number itself. Second step would be to read the edges {u, v} and to do a union(u, v). We compare the actual root numbers of each vertex in the union method and make one of them the root of for both. Imagine we have two vertices x and y and an undirected edge which connects both vertices. The root for x is x and y is the root of y. If we union these vertices, one of them needs to be the main root. In this algorithm we consider x to be the new root. x still stays the root of itself. Of course all of this might be different, based on how you implement it. Below you can find a couple of implementations.

ImplementationsTurn your phone horizontically


class UnionFind {
int[] root;
    
  public UnionFind(int n) { //n == #vertices
      root = new int[n];
      for (int i = 0; i < n; i++) {
             root[i] = i;
      }
  }
        
  public void union(int x, int y) {
      int rootOfX = find(x);
      int rootOfY = find(y);
      if (rootOfX != rootOfY) {
          for (int i = 0; i < root.length; i++) {
              if (root[i] == rootOfY) {
                  root[i] = rootOfX;
              }
          }
      }
  }

  public int find(int x) {
    return root[x];
  }

  public boolean isConnected(int x, int y) {
      return find(x) == find(y);
  }
}
            

class UnionFind {
int[] root;

  public UnionFind(int n) {
      root = new int[n];
      for (int i = 0; i < n; i++) {
             root[i] = i;
      }
  }
        
  public void union(int x, int y) {
      int rootOfX = find(x);
      int rootOfY = find(y);
      if (rootOfX != rootOfY) {
          root[rootofY] = rootOfX;
      }
  }

  public int find(int x) {
    while (x != root[x]) {
        x = root[x];
    }
    return x;
  }

  public boolean isConnected(int x, int y) {
      return find(x) == find(y);
  }
}
              

class UnionFind {
int[] root;
int[] rank;
  public UnionFind(int n) {
      root = new int[n];
      rank = new int[n];
      for (int i = 0; i < n; i++) {
          root[i] = i;
          rank[i] = 1;
      }
  }
      
  public void union(int x, int y) {
      int rootOfX = find(x);
      int rootOfY = find(y);
      if (rootOfX != rootOfY) {
          if(rank[rootOfX] > rank[rootOfY]){
              root[rootOfY] = rootOfX;
          } else if(rank[rootOfX] < rank[rootOfY]){
              root[rootOfX] = rootOfY;
          } else {
              root[rootOfY] = rootOfX;
              rank[rootOfX]++;
          }
      }
  }

  public int find(int x) {
      if(x == root[x]){
          return x;
      }
    return root[x] = find(root[x]);
  }

  public boolean isConnected(int x, int y) {
      return find(x) == find(y);
  }
}