dsa/graphs/misc | desc: cycle in directed graph

cycle detection directed.cpp

#include <bits/stdc++.h>
using namespace std;

/*
Using DFS to find a cycle in directed graph:
============================================
- DFS can be used to detect a cycle in a directed graph. DFS for a connected graph produces a tree. There is a cycle in a graph only
  if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (self-loop) or one of its
  ancestor in the tree produced by DFS.
- Simple visited approach will not work here:
  Ex:
  1 <--- 2
  ^      ^
  |      |
  3 <--- 4
  Start from node = 4
  We need both visited and recStack here. 
*/

int N;
vector<vector<int>> gph;
vector<bool> vis(N, false);
vector<bool> recStack(N, false);

bool dfs(int src, vector<bool>& vis, vector<bool>& recStack){
  vis[src] = true;
  recStack[src] = true;
  for(auto v : gph[src]) {
    if(!vis[v]){
      if(dfs(v, vis, recStack)) return true;
    } else if(recStack[v]) return true;
  }
  recStack[src] = false;
  return false;
}

// dfs(0, vis, recStack);