323. Number of Connected Components in an Undirected Graph

time: O(edges*nodes)

space: O(n)

similar to 261

only change this part

if (x != y) {
    roots[x] = y;
    res--; // final result
}

and the key idea is

graph numbers = nodes - edges

class Solution {
    public int countComponents(int n, int[][] edges) {
        // no edge case condition, no edges.length != n - 1 case

        // graph numbers = nodes - edges
        int res = n;
        int roots[] = new int[n];
        for (int i = 0; i < n ; i++) {
            roots[i] = -1;
        }
        for (int pair[] : edges) {
            int x = find(roots, pair[0]);
            int y = find(roots, pair[1]);
            if (x != y) {
                roots[x] = y;
                res--;
            }
        }
        return res;
    }
    
    private int find(int roots[], int i) {
        while (roots[i] != -1) {
            i = roots[i];
        }
        return i;
    }
}

BFS

time: O(m+n), m is edge size(m*2), n is num of node, loop to do bfs

space: O(n)

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<Integer>[] graph = new List[n]; // edges to graph
        boolean[] visited = new boolean[n];
        
        for (int i = 0 ; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]); // 無向圖, 必須做雙向
            graph[edge[1]].add(edge[0]);
        }
        int count = 0;
        for (int i = 0 ; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                bfs(graph, i, visited);
                count++;
            }
        }
        return count;
    }
    private void bfs(List<Integer>[] graph, int i, boolean[] visited) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(i);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int others : graph[node]) {
                if (!visited[others]) { // these are all connected with node's node, so only check is it connected before
                    queue.offer(others);
                    visited[others] = true;
                }
            }
        }
    }
}