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

# 323. Number of Connected Components in an Undirected Graph

{% hint style="info" %}
Union-Find : union(int p, int q), find(int p)

time complexity: find: O(1), so overall: O(E)

space complexity: O(V)
{% endhint %}

```java
class Solution {
    // union-find
    int count;
    int[] graph;
    int[] size;
    public int countComponents(int n, int[][] edges) {
        // initialize the array representation of graph;
        graph = new int[n];
        size = new int[n];
        for(int i = 0; i<graph.length; i++){
            graph[i] = i;
            size[i] = 1;
        }
        count = n;
        
        for(int[] edge : edges){
            union(edge[0], edge[1]);
        }
        return count;
    }
    
    private void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP!=rootQ){
            if(size[rootP]>size[rootQ]){
                graph[rootQ] = rootP;
            }else{
                graph[rootP] = rootQ;
            }
            int sum = size[rootP]+size[rootQ];
            size[rootQ]=sum;
            size[rootQ]=sum;
            count--;
        }
    }
    
    // find the root of vertex i
    private int find(int i){
        while(graph[i]!=i){
            // remember: reduce time complexity
            graph[i]=graph[graph[i]];
            i=graph[i];
        }
        return i;
    }
}
```

{% hint style="info" %}
DFS=> build graph, then check the visited vertex

**Complexity Analysis**

Here EE = Number of edges, VV = Number of vertices.

* Time complexity: {O}(E + V)O(E+V).

  Building the adjacency list will take {O}(E)O(E) operations, as we iterate over the list of edges once, and insert each edge into two lists.

  During the DFS traversal, each vertex will only be visited once. This is because we mark each vertex as visited as soon as we see it, and then we only visit vertices that are not marked as visited. In addition, when we iterate over the edge list of each vertex, we look at each edge once. This has a total cost of {O}(E + V)O(E+V).
* Space complexity: {O}(E + V)O(E+V).

  Building the adjacency list will take {O}(E)O(E) space. To keep track of visited vertices, an array of size {O}(V)O(V) is required. Also, the run-time stack for DFS will use {O}(V)O(V) space.
  {% endhint %}

```java
class Solution {
    boolean[] visited;
    int count;
    public int countComponents(int n, int[][] edges) {
        visited = new boolean[n];
        List<Integer>[] graph = buildGraph(edges, n);
        
        for(int i=0; i<graph.length; i++){
            if(!visited[i]){
                count++;
                traverse(graph, i);
            }
        }
        return count;
        
    }
    
    private void traverse(List<Integer>[] graph, int curr){
        visited[curr]=true;
        for(int next: graph[curr]){
            if(!visited[next]){
                traverse(graph, next);
            }
        }
    }
    
    private List<Integer>[] buildGraph(int[][] edges, int n){
        List<Integer>[] graph = new LinkedList[n];
        for(int i = 0; i<graph.length; i++){
            graph[i] = new LinkedList<>();
        }
        
        for(int i=0; i<edges.length; i++){
            int from = edges[i][0];
            int to = edges[i][1];
            
            // undirected graph;
            graph[from].add(to);
            graph[to].add(from);
        }
        
        return graph;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ucan.gitbook.io/notes/graph/323.-number-of-connected-components-in-an-undirected-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.