An algorithm for graph traversal in which a node’s children are recursively visited before other sibling nodes. For example:
The following code assumes that the graph represented by the adjacency list is connected.
#include <vector>
std::vector<int> adjacency_list[N];
bool visited[N];
void dfs(int node) {
visited[node] = true;
for (int n : adjacency_list[node])
if (!visited[n])
dfs(n);
}If the graph is not connected, then after the first DFS, do a DFS on the next unvisited node (check the visited array) until all nodes are visited.
In a similar fashion, you can use the above code to find out if the graph is connected. If it is connected then the visited array will all be true after the first DFS. If not then the graph has multiple components. The nodes that are currently visited belong to the same component. Do a couple more DFS’s to find out what the other components are.