3. Topological Sort

DFS

void dfs(int node,
         vector<vector<int>>& adj,
         vector<bool>& visited,
         stack<int>& st) { //! Stack here

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            dfs(neighbor, adj, visited, st);
        }
    }

    st.push(node);
}

Driver

stack<int> st;

for (int i = 0; i < V; i++) {

    if (!visited[i])
        dfs(i, adj, visited, st);
}

while (!st.empty()) {

    cout << st.top() << " ";
    st.pop();
}

Kahn's Algorithm (BFS)

vector<int> topoSort(int V, vector<vector<int>>& adj) {

    vector<int> indegree(V, 0);

    // Calculate indegree
    for (int i = 0; i < V; i++) {

        for (int neighbor : adj[i]) {

            indegree[neighbor]++;
        }
    }

    queue<int> q;

    // Push all nodes with indegree 0
    for (int i = 0; i < V; i++) {

        if (indegree[i] == 0)
            q.push(i);
    }

	// int processed = 0; // For determining cyclicity
	
    vector<int> topo;

    while (!q.empty()) {

        int node = q.front();
        q.pop();
		
		// processed++;
		
        topo.push_back(node);

        for (int neighbor : adj[node]) {

            indegree[neighbor]--;

            if (indegree[neighbor] == 0)
                q.push(neighbor);
        }
    }
	
	// If all nodes were processed → DAG (Directed acyclic graph)
	// return processed == V;
	
    return topo;
}