0323. Number of Connected Components in an Undirected Graph

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

Description

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

Constraints:

• 1 <= n <= 2000

• 1 <= edges.length <= 5000

• edges[i].length == 2

• 0 <= ai <= bi < n

• ai != bi

• There are no repeated edges.

ac

class Solution {
    public int countComponents(int n, int[][] edges) {
        // edge cases
        if (n <= 1) return n;

        UnionFind uf = new UnionFind(n);
        for (int[] e : edges) {
            uf.connect(e[0], e[1]);
        }

        return uf.getCount();
    }

    class UnionFind {
        int[] root;
        int count;
        public UnionFind(int n) {
            root = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                root[i] = i;
            }
        }
        void connect(int p1, int p2) {
            int f1 = find(p1);
            int f2 = find(p2);
            if (f1 != f2) {
                root[f2] = f1;
                count--;
            }
        }
        int find(int p) {
            if (p != root[p]) {
                root[p] = find(root[p]); // path compression
            }
            return root[p];
        }
        int getCount() {
            return this.count;
        }
    }
}