> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/union-find/323.-number-of-connected-components-in-an-undirected-graph.md).

# 323. Number of Connected Components in an Undirected Graph

![](/files/-MaaspzmICq9IwVBW7q3)

![](/files/-MaasuTlii0cVbji8qkX)

time: O(edges\*nodes)

space: O(n)

similar to 261

only change this part

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

and the key idea is 

```java
graph numbers = nodes - edges
```

```java
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)

```java
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;
                }
            }
        }
    }
}
```