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.

Note: You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution

public class Solution {
    public class Node {
        Node parent;
        public Node() {
            this.parent = this;
        }
    }

    public Node getparent(Node node) {
        while(node.parent != node) node = node.parent;
        return node;
    }

    public int countComponents(int n, int[][] edges) {
        if(n == 0) return 0;
        Node nodes[] = new Node[n];
        for(int i = 0; i < n; i++) nodes[i] = new Node();
        for(int i = 0; i < edges.length; i++) {
            Node one = getparent(nodes[edges[i][0]]);
            Node two = getparent(nodes[edges[i][1]]);

            if(one != two) {
                n--;
                one.parent = two;
            }
        }
        return n;
    }
}