Untitled

////////////////////// APPROACH - 1 (DFS)

bool detectCycle(int node, vector<int> adjList[], int visited[]) {
   // if node is DfsVisited, cycle exists.
   // Note if visited[node] == 1, then cycle doesn’t exist bcz the node is not in current
   // dfs call hierarchy.
  if (visited[node] == 2)
    return true;

     // made node DfsVisited, i.e. node is in current dfs call hierarchy
    visited[node] = 2;

    for (int j = 0; j < adjList[node].size(); j++) {
      if (detectCycle(adjList[node][j], adjList, visited))
        return true;
    }

    // make node visited, i.e. it has been visited while traversing, but now its not in
    // current dfs call hierarchy.
    visited[node] = 1;
    return false;
}

int detectCycleInDirectedGraphApproach1(int n, vector < pair < int, int >> & edges) {
  vector<int> adjList[n+1];

  for (auto edge : edges) {
    adjList[edge.first].push_back(edge.second);
  }

  // 0 -> unvisited, 1 -> visited, 2 -> DfsVisited
  // visited -> node has been visited but its not in current dfs call hierarchy.
  // DfsVisited -> node has been visited and is in current dfs call hierarchy.
  int visited[n+1] = {0}; 

  for (int i = 1; i <= n; i++) {
    if (visited[i] == 0) // check for cycle from unvisited nodes
      if (detectCycle(i, adjList, visited))
        return true;
  }

  return false;
}