Topological sort

Given a Directed Acyclic Graph (DAG) of V (0 to V-1) vertices and E edges represented as a 2D list of edges[][], where each entry edges[i] = [u, v] denotes an directededge u -> v. Return topological sort for the given graph.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering.

Note: As there are multiple Topological orders possible, you may return any of them. If your returned Topological sort is correct then the output will be true else false.

Examples:

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

Output: true
Explanation: The output true denotes that the order is valid. Few valid Topological orders for the given graph are:
[3, 2, 1, 0]
[1, 2, 3, 0]
[2, 3, 1, 0]

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

Output: true
Explanation: The output true denotes that the order is valid. Few valid Topological orders for the graph are:
[4, 5, 0, 1, 2, 3]
[5, 2, 4, 0, 1, 3]

Constraints:
2 ≤ V ≤ 10³
1 ≤ E = edges.size() ≤ (V * (V – 1)) / 2

Approach 01:

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<int> topoSort(int vertexCount, vector<vector<int>>& edges) {
        vector<int> inDegree(vertexCount, 0);
        vector<int> adjacencyList[vertexCount];
        vector<int> topologicalOrder;

        // Build the graph and compute in-degrees
        for (int i = 0; i < edges.size(); i++) {
            int fromNode = edges[i][0];
            int toNode = edges[i][1];
            inDegree[toNode]++;
            adjacencyList[fromNode].push_back(toNode);
        }

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

        // Kahn's algorithm (BFS-based topological sort)
        while (!bfsQueue.empty()) {
            int currentNode = bfsQueue.front();
            bfsQueue.pop();
            topologicalOrder.push_back(currentNode);

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

        // Optional: if graph contains a cycle, remaining nodes will still have in-degree > 0
        for (int node = 0; node < vertexCount; node++) {
            if (inDegree[node] > 0) {
                topologicalOrder.push_back(node);
            }
        }

        return topologicalOrder;
    }
};

from collections import deque
from typing import List

class Solution:
    def topoSort(self, vertexCount: int, edges: List[List[int]]) -> List[int]:
        inDegree = [0] * vertexCount
        adjacencyList = [[] for _ in range(vertexCount)]
        topologicalOrder = []

        # Build the graph and compute in-degrees
        for fromNode, toNode in edges:
            inDegree[toNode] += 1
            adjacencyList[fromNode].append(toNode)

        bfsQueue = deque()
        for node in range(vertexCount):
            if inDegree[node] == 0:
                bfsQueue.append(node)

        # Kahn's algorithm (BFS-based topological sort)
        while bfsQueue:
            currentNode = bfsQueue.popleft()
            topologicalOrder.append(currentNode)

            for neighbor in adjacencyList[currentNode]:
                inDegree[neighbor] -= 1
                if inDegree[neighbor] == 0:
                    bfsQueue.append(neighbor)

        # Optional: if graph contains a cycle, include remaining nodes
        for node in range(vertexCount):
            if inDegree[node] > 0:
                topologicalOrder.append(node)

        return topologicalOrder

Time Complexity:

• Building the Graph:

  Each edge is processed once to populate the adjacency list and compute in-degrees, which takes \( O(E) \) time.

• Queue Initialization:

  All vertices are checked for zero in-degree, which takes \( O(V) \) time.

• BFS Traversal:

  Each vertex is added to the queue at most once and each edge is traversed once, contributing \( O(V + E) \) time.

• Cycle Check:

  All vertices are scanned again to check for remaining in-degrees, which takes \( O(V) \) time.

• Total Time Complexity:

  \( O(V + E) \)

Space Complexity:

• Adjacency List:

  Stores all edges once, taking \( O(V + E) \) space.

• In-degree Array and Output Vector:

  Both use \( O(V) \) space.

• Queue:

  In the worst case, the queue holds all vertices, which is \( O(V) \) space.

• Total Space Complexity:

  \( O(V + E) \)