Topological sort GFG

• Link: https://www.geeksforgeeks.org/problems/topological-sort/1?utm_source=youtube&utm_medium=collab_striver_ytdescription&utm_campaign=topological-sort

Question

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 a directed edge u -> v. Return the 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  ≤  103
1  ≤  E = edges.size()  ≤  (V * (V - 1)) / 2

Try more examples

Approach 1: Optimal

Intuition

• Topo sort

Algorithm

1. Declare & initialize visted array with size V and value 0
2. Declare & intialize stack<int> s
3. For considering disconnected component loop through the visited array
   1. If not visited
      1. call dfs
4. Declare vector<int> ans
5. While stack is not empty
   1. Push the top of the stack in ans
   2. Pop the stack
6. return ans

• DFS
  1. Base case (no base case)
  2. Processing
     1. set visited for the node
  3. Recurse case
     1. call dfs on the neighbors if the neighbor is not visited
  4. Back tracking
     1. Push the node in the stack.

Code

class Solution {
public:
    vector<vector<int>> getAdj(int V, vector<vector<int>>& edges) {
        vector<vector<int>> adj(V);
        for (auto edge : edges) {
            adj[edge[0]].push_back(edge[1]);
        }
        return adj;
    }

    void dfs(int node, vector<vector<int>>& adj, vector<int>& visited, stack<int>& s) {
        visited[node] = 1;
        for (auto neighbor : adj[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, adj, visited, s);
            }
        }
        s.push(node);
    }

    vector<int> topoSort(int V, vector<vector<int>>& edges) {
        vector<vector<int>> adj = getAdj(V, edges);
        vector<int> visited(V, 0);
        stack<int> s;

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited, s);
            }
        }

        vector<int> ans;
        while (!s.empty()) {
            ans.push_back(s.top());
            s.pop();
        }

        return ans;
    }
};

Complexity Analysis

• Time Complexity: $O(V+E)$
• Space Complexity: $O(V+E)$
  • Where,
    • V -> no. of nodes
    • E -> no. of edges