Graphs

1// Graph DFS — adjacency list, O(V + E)
2vector<vector<int>> adj;   // adj[u] = list of neighbours of u
3vector<bool> visited;
4 
5void dfs(int node)
6{
7    visited[node] = true;
8 
9    for (int neighbour : adj[node])
10    {
11        if (!visited[neighbour])
12        {
13            dfs(neighbour);
14        }
15    }
16}
17 
18// Call for every unvisited node to handle disconnected components
19int countComponents(int n)
20{
21    adj.assign(n, {});
22    visited.assign(n, false);
23    int components = 0;
24 
25    for (int i = 0; i < n; i++)
26    {
27        if (!visited[i])
28        {
29            dfs(i);
30            components++;
31        }
32    }
33 
34    return components;
35}