Untitled

#include <bits/stdc++.h>

////////////////////// APPROACH - 2 (BFS)

bool topoSortCycleDetect(int V, vector<int> adj[]) {
    queue<int> q;
    int indegree[V+1] = {0};
    
    for (int i = 1; i <= V; i++) {
        for (int j = 0; j < adj[i].size(); j++) {
            indegree[adj[i][j]]++;
        }
    }
    
    // insert all 0 indegree nodes in queue
    for (int i = 1; i <= V; i++)
        if (indegree[i] == 0)
            q.push(i);

    int proccessedNodesCnt = 0;
    
    while (!q.empty()) {
        // Nodes in queue have no dependency on any other node (i.e. indegree = 0)
        // so process them
        int node = q.front();
        q.pop();
        proccessedNodesCnt++;

        for (int i = 0; i < adj[node].size(); i++) {
            // Reduce indegree count by 1 of all the nodes which are dependent on processed node.
            int connectedNode = adj[node][i];
            indegree[connectedNode]--;
            
            // If after reducing indegree count, we got indegree = 0 node. Push it in queue.
            if (indegree[connectedNode] == 0)
                q.push(connectedNode);
        }
    }
    
    return proccessedNodesCnt != V;
}


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

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

  return topoSortCycleDetect(n, adjList);
}



////////////////////// 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;
}