> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-24-2022-323.-number-of-connected-components-in-an-undirected-graph.md).

# 06/24/2022 323. Number of Connected Components in an Undirected Graph

323\. Number of Connected Components in an Undirected Graph

method 1:

use union-find algo. first initialize root and rank array with the size of n. set each element of root array to -1, and element of rank to 1. Traverse all of the edges one by one, performing the union-find method union on each edge. Finally check the number of -1 in the root array and this count is the number of connected components.

Time O(V + E\*alpha(V))

Space O(V)

```
// Some code
class Solution {
    //total: T: (V+ E*alpha(V)) Space O(V)
    public int countComponents(int n, int[][] edges) {
        //T: O(V) S: O(V)
        int[] root = new int[n];
        int[] rank = new int[n];
        Arrays.fill(root, -1);
        Arrays.fill(rank, 1);
        
        //T: O(E* alpha(v)) S: O(1)
        for (int i = 0; i < edges.length; i++) {
            union(root, rank,edges[i][0], edges[i][1]);
        }
        int count = 0;
        //O(V)
        for (int i : root) {
            if (i == -1) {
                count++;
            }
        }
        return count;
    }
    
    
    //T AND S: O(V)
    private int find(int root[], int i) {
        if (root[i] == -1)
            return i;
        return root[i] = find(root, root[i]);
    }
    
    //T: alpha(V)
    private void union (int root[], int rank[], int x, int y) {
        int xset = find(root, x);
        int yset = find(root, y);
        if(xset != yset) {
            if (rank[xset] > rank[yset]) {
                root[yset] = xset;
            } else if (rank[xset] < rank[yset]) {
                root[xset] = yset;
            } else {
                root[yset] = xset;
                rank[xset]++;
            }
        }
    }
}
```

method 2:

1. Initialize a variable `count` with the number of vertices in the input.
2. Traverse all of the edges one by one, performing the union-find method `combine` on each edge. If the endpoints are already in the same set, then keep traversing. If they are not, then decrement `count` by 1.
3. After traversing all of the `edges`, the variable `count` will contain the number of components in the graph.

```
// Some code
class Solution {
     public int countComponents(int n, int[][] edges) {
         int[] root = new int[n];
         int[] rank = new int[n];
         for (int i = 0; i < n ; i++) {
             root[i] = i;
             rank[i] = 1;
         }
         int count = n;
         for (int i = 0; i < edges.length; i++) {
             count -= union(root, rank, edges[i][0], edges[i][1]);
         }
         return count;
     }
    
     private int find(int[] root, int v) {
         if (v == root[v]) {
             return v;
         }
         return root[v] = find(root, root[v]);
     }
    
    private int union(int[] root, int[] rank, int x, int y) {
        int xset = find(root, x);
        int yset = find(root, y);
        
        if (xset == yset)
            return 0;
        else {
            if (rank[xset] > rank[yset]) {
                root[yset] = xset;
            } else if (rank[xset] < rank[yset]) {
                root[xset] = yset;
            } else {
                root[yset] = xset;
                rank[xset]++;
            }
            return 1;
        }
    }
}
```