# 323. Number of Connected Components in an Undirected Graph

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MaS8V4oYWIC9zeljAMU%2F-MaaspzmICq9IwVBW7q3%2Fimage.png?alt=media\&token=dfb029cb-eaf0-4452-8524-53bac4ff4639)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MaS8V4oYWIC9zeljAMU%2F-MaasuTlii0cVbji8qkX%2Fimage.png?alt=media\&token=d34bae82-ac6e-46d4-a550-9ac80d94990f)



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&#x20;

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