323.Number of Connected Components in an Undirected Graph

Tags: [union_find], [path_compression], [union_by_rank]

Com: {t}

Hard: [###]

Link: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/\#/description

Given nnodes labeled from0ton - 1and 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 = 5and edges = [[0, 1], [1, 2], [3, 4]], return2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1.

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: Union Find, Path Compression, Union By Rank

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n == 0) {
            return 0;
        }
        if (edges.length == 0) {
            return n;
        }

        int[] parents = new int[n];
        for (int i = 0; i < n; i ++) {
            parents[i] = i;
        }

        int[] ranks = new int[n];

        for (int i = 0; i < edges.length; i ++) {
            int x = edges[i][0];
            int y = edges[i][1];

            int xParent = getParent(parents, x);
            int yParent = getParent(parents, y);

            // union by rank
            int xpRank = ranks[xParent];
            int ypRank = ranks[yParent];

            if (xpRank <= ypRank) {
                // Append smaller tree to big tree.
                parents[xParent] = yParent;
                ranks[yParent] ++;
            } else {
                parents[yParent] = xParent;
                ranks[xParent] ++;
            }
        }

        Set<Integer> set = new HashSet<>();
        for (int node = 0; node < n; node ++) {
            set.add(getParent(parents, node));
        }

        return set.size();
    }

    private int getParent(int[] parents, int curr) {
        // path compression.
        if (parents[curr] != parents[parents[curr]]) {
            parents[curr] = getParent(parents, parents[curr]);
        }

        return parents[curr];
    }
}

Revelation:

• Union by rank: append the smaller tree to the bigger tree, the bigger rank means the tree is bigger.
• parents[xParent] = yParent, means let yParent be the parent of xParent, which means appending the x-tree to y-tree.

Note:

• Time complexity = O(n * m * lg*(n) + n * n * lg*(n)), n is the given n, m is the number of edges. The time complexity of union find reference is here: https://zhaonanli.gitbooks.io/algorithm/content/union-find.html

Solution: Union Find, Path Compression

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n == 0) {
            return 0;
        }
        if (edges.length == 0) {
            return n;
        }

        int[] parents = new int[n];
        for (int i = 0; i < n; i ++) {
            parents[i] = i;
        }

        for (int i = 0; i < edges.length; i ++) {
            int x = edges[i][0];
            int y = edges[i][1];

            int xParent = getParent(parents, x);
            int yParent = getParent(parents, y);

            // union
            parents[xParent] = yParent;
        }

        Set<Integer> set = new HashSet<>();
        for (int node = 0; node < n; node ++) {
            set.add(getParent(parents, node));
        }
        return set.size();
    }

    private int getParent(int[] parents, int curr) {
        if (parents[curr] != parents[parents[curr]]) {
            parents[curr] = getParent(parents, parents[curr]);
        }

        return parents[curr];
    }
}