Function that traverses a node via depth first traversal and returns the number of connected components
| 25 | |
| 26 | // Function that traverses a node via depth first traversal and returns the number of connected components |
| 27 | int dfs(vector<ll>* graph,bool* visited, ll i ) |
| 28 | { |
| 29 | visited[i] = true; |
| 30 | int cc = 1; // initialize number of components to 1 |
| 31 | for(int j=0;j<graph[i].size();j++) |
| 32 | { |
| 33 | int x = graph[i][j]; |
| 34 | if(!visited[x]) |
| 35 | { |
| 36 | cc += dfs(graph,visited,x); |
| 37 | // for each edge connected recursively call and add to the number of connected components |
| 38 | } |
| 39 | } |
| 40 | return cc; |
| 41 | } |
| 42 | |
| 43 | int main() |
| 44 | { |