DFS

DFS is one of the main graph search algorithms. The idea of DFS is to start a vertex, then recursively visit each adjacent unvisited vertex in order. 

vector<vector<int>> adj;

vector<bool> vis;

void dfs(int v){
    vis[v] = true;
    for(int u : adj[v]){
        if(!vis[u]){
    dfs(u);
        }
}

DFS can be used to do many things including:

  • Finding connected components
  • Finding cycles
  • Finding Lowest Common Ancestors
  • Finding bridges, articulation points