323. Number of Connected Components in an Undirected Graph

// LeetCode URL: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
import java.util.HashMap;
import java.util.HashSet;

/**
 * Using DFS
 *
 * Time Complexity: O(N + E)
 *
 * Space Complexity: O(N + E)
 *
 * N = Number of vertices in the graph. E = Number of edges in the graph.
 */
class Solution1 {
    public int countComponents(int n, int[][] edges) {
        if (edges == null || n <= 0) {
            return 0;
        }
        if (n == 1 || edges.length == 0) {
            return n;
        }

        HashMap<Integer, HashSet<Integer>> graph = buildGraph(n, edges);
        HashSet<Integer> visited = new HashSet<>();

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited.contains(i)) {
                dfsHelper(graph, i, visited);
                count++;
            }
        }

        return count;
    }

    private void dfsHelper(HashMap<Integer, HashSet<Integer>> graph, int node, HashSet<Integer> visited) {
        if (visited.contains(node)) {
            return;
        }
        visited.add(node);
        for (int neigh : graph.get(node)) {
            if (!visited.contains(neigh)) {
                dfsHelper(graph, neigh, visited);
            }
        }
    }

    private HashMap<Integer, HashSet<Integer>> buildGraph(int n, int[][] edges) {
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashSet<>());
        }
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        return graph;
    }
}

/**
 * Using Union Find
 *
 * Time Complexity: O(N + E). N to create the parents array. E to perform union
 * E times.
 *
 * Space Complexity: O(N)
 *
 * N = Number of vertices in the graph. E = Number of edges in the graph.
 */
class Solution2 {
    public int countComponents(int n, int[][] edges) {
        if (edges == null || n <= 0) {
            return 0;
        }
        if (n == 1 || edges.length == 0) {
            return n;
        }

        UnionFind graph = new UnionFind(n);

        int count = n;
        for (int[] e : edges) {
            if (graph.union(e[0], e[1])) {
                count--;
            }
        }
        return count;
    }

    class UnionFind {
        int[] parents;
        int[] ranks;

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

        public int find(int i) {
            if (i == parents[i]) {
                return i;
            }
            parents[i] = find(parents[i]);
            return parents[i];
        }

        public boolean union(int a, int b) {
            int x = find(a);
            int y = find(b);

            if (x == y) {
                return false;
            }

            if (ranks[x] >= ranks[y]) {
                ranks[x] = ranks[x] == ranks[y] ? ranks[x] + 1 : ranks[x];
                parents[y] = x;
            } else {
                parents[x] = y;
            }
            return true;
        }
    }
}