323. Number of Connected Components in an Undirected Graph

二刷 05/2022

Version #2 Iterative DFS

Time O(E + V)

Space O(E + V)

Runtime: 18 ms, faster than 10.67% of Java online submissions for Number of Connected Components in an Undirected Graph.

Memory Usage: 47.1 MB, less than 38.69% of Java online submissions for Number of Connected Components in an Undirected Graph.

class Solution {

    public int countComponents(int n, int[][] edges) {

        if (edges == null || edges.length == 0) {

            return n;

        }

        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            graph.add(new ArrayList<>());

        }

        for (int[] edge : edges) {

            graph.get(edge[0]).add(edge[1]);

            graph.get(edge[1]).add(edge[0]);

        }

        int cnt = 0;

        Set<Integer> visited = new HashSet<>();

        for (int i = 0; i < n; i++) {

            if (!visited.contains(i)) {

                cnt++;

                traverse(graph, i, visited);

            }

        }

        return cnt;

    }

    private void traverse(List<List<Integer>> graph, int node, Set<Integer> visited) {

        Stack<Integer> stack = new Stack<>();

        stack.push(node);

        visited.add(node);

        while (!stack.isEmpty()) {

            Integer curr = stack.pop();

            for (Integer next : graph.get(curr)) {

                if (visited.contains(next)) {

                    continue;

                }

                stack.push(next);

                visited.add(next);

            }

        }

    }

}

一刷
Version #1 Union-Find
When nodes are initialized, all of them are distinct, so the initial connected component is N
Every time we merge to component that don't have the same id, it means that two distinct connected components are merged together, so we should have count--
In the end, return count directly

[2ND TRY]

100.00 %
class Solution {
    class UF {
private int[] id;
private int[] size;
private int count;
public UF(int N) {
id = new int[N];
size = new int[N];
count = N;
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}

private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
count--;
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
public int getCount() {
return count;
}
}

public int countComponents(int n, int[][] edges) {
UF uf = new UF(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.getCount();
}
}


[1ST TRY]

80.23 % 
class Solution {
    public int countComponents(int n, int[][] edges) {
        // Union Find
        // If father(x) == x, it is a root
        // root has a size of #nodes in its connected component
        if (n <= 0) return 0;
        if (edges == null || edges.length == 0) return n;
        int[] father = new int[n];
        int[] size = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
            size[i] = 1;
        }
        int result = n; // n distinct nodes
        for (int[] edge : edges) {
            if (union(edge[0], edge[1], father, size)) result--;
        }
        return result;
    }
    private int root(int x, int[] father) {
        if (father[x] == x) return x;
        int root = root(father[x], father);
        father[x] = root; // path compression
        return root;
    }
 
    // Return false if x,y are already in the same component
    private boolean union(int x, int y, int[] father, int[] size) {
        int rootX = root(x, father);
        int rootY = root(y, father);
        if (rootX == rootY) return false;
        if (size[rootX] > size[rootY]) {
            father[rootY] = rootX;
            size[rootX] += size[rootY];
        } else {
            father[rootX] = rootY;
            size[rootY] += size[rootX];
        }
        return true;
    }
}