Directed Graph Cycle

Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.
The graph is represented as a 2D vector edges[][], where each entry edges[i] = [u, v] denotes an edge from verticex u to v.

Examples:

Input: V = 4, edges[][] = [[0, 1], [1, 2], [2, 3], [3, 3]]

Output: true
Explanation: 3 -> 3 is a cycle

Input: V = 3, edges[][] = [[0, 1], [1, 2]]


Output: false
Explanation: no cycle in the graph

Constraints:
1 ≤ V, E ≤ 10⁵

Approach 01:

#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool isCyclic(int vertexCount, vector<vector<int>>& edges) {
        vector<int> inDegree(vertexCount, 0);
        unordered_map<int, vector<int>> adjacencyList;

        for (const auto& edge : edges) {
            int fromNode = edge[0];
            int toNode = edge[1];
            inDegree[toNode]++;
            adjacencyList[fromNode].push_back(toNode);
        }

        queue<int> processingQueue;
        vector<int> topologicalOrder;

        for (int node = 0; node < vertexCount; ++node) {
            if (inDegree[node] == 0) {
                processingQueue.push(node);
            }
        }

        while (!processingQueue.empty()) {
            int currentNode = processingQueue.front();
            processingQueue.pop();
            topologicalOrder.push_back(currentNode);

            for (int neighbor : adjacencyList[currentNode]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    processingQueue.push(neighbor);
                }
            }
        }

        return topologicalOrder.size() != vertexCount;
    }
};

from collections import defaultdict

class Solution:
    def isCycle(self, V, edges):
        inDegree = [0] * V
        adjacencyList = defaultdict(list)
        
        for fromNode, toNode in edges:
            inDegree[toNode] += 1
            adjacencyList[fromNode].append(toNode)

        topoOrder = []
        queue = []

        for node in range(V):
            if inDegree[node] == 0:
                queue.append(node)

        while queue:
            currentNode = queue.pop(0)
            topoOrder.append(currentNode)

            for neighbor in adjacencyList[currentNode]:
                inDegree[neighbor] -= 1
                if inDegree[neighbor] == 0:
                    queue.append(neighbor)
                    
        return len(topoOrder) != V

Time Complexity:

• Graph Construction:

  Each of the E edges is processed once to build the adjacency list and compute in-degrees, so this takes \( O(E) \) time.

• Kahn’s Algorithm (Topological Sort):

  Each node is added to the queue and popped exactly once, and each edge is considered once, resulting in \( O(V + E) \) time.

• Total Time Complexity:

  \( O(V + E) \), where \( V \) is the number of vertices and \( E \) is the number of edges.

Space Complexity:

• Adjacency List and In-Degree Array:

  The adjacency list stores all edges, and the in-degree array stores a count for each node. This takes \( O(V + E) \) space.

• Auxiliary Storage:

  The queue and the topological order array each take up to \( O(V) \) space.

• Total Space Complexity:

  \( O(V + E) \)