2.2 Number of Connected Components in an Undirected Graph

Description

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1: 0 3 | | 1 --- 2 4 Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2: 0 4 | | 1 --- 2 --- 3 Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Method

Union Find

Time and Space Complexity

o(n)

Code

public class Solution {

class UF{
      HashMap<Integer, Integer> map;
      int count;

      public UF(int n){
             map = new HashMap<Integer, Integer>();
             count = n;
             for (int i = 0; i < n; i++){
                 map.put(i, i);
             }
      }

      public int compressfind(int i){
             int parent = i;
             while (parent != map.get(parent)){
                    parent = map.get(parent);
             }
             int fa = i;
             int tmp = i;
             while (fa != map.get(fa)){
                    tmp = map.get(fa);
                    map.put(fa, parent);
                    fa = tmp;
             } 
             return parent;
      }

      public void union(int i, int j){
             int x_fa = compressfind(i);
             int y_fa = compressfind(j);
             if (x_fa != y_fa){
                 map.put(x_fa, y_fa);
                 count--;
             }
      }
}

public int countComponents(int n, int[][] edges) {

       if (n <= 1){
           return n; 
       };



       UF uf = new UF(n);
       for (int i = 0; i < edges.length; i++){
            int x = edges[i][0];
            int y = edges[i][1];
            uf.union(x, y);
       }
       //System.out.println(uf.count);
       return uf.count;
}

}