You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

 

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

 1 class Solution {
 2     public int countComponents(int n, int[][] edges) {
 3     int[] roots = new int[n];
 4     for(int i = 0; i < n; i++) roots[i] = i; 
 5 
 6     for(int[] e : edges) {
 7         int root1 = find(roots, e[0]);
 8         int root2 = find(roots, e[1]);
 9         if(root1 != root2) {      
10             roots[root1] = root2;  // union
11             n--;
12         }
13     }
14     return n;
15 }
16 
17 public int find(int[] roots, int id) {
18     while(roots[id] != id) {
19         roots[id] = roots[roots[id]];  // optional: path compression
20         id = roots[id];
21     }
22     return id;
23 }
24 }