topological_sorting(DFS)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> adj; // adjacency list of graph
vector<int> visited;
vector<int> ans; // will store the topological order

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v); // add vertex to the result after visiting all neighbors
}

vector<int> topological_sort(int n) {
    visited.assign(n, false);
    ans.clear();

    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }

    reverse(ans.begin(), ans.end()); // reverse to get correct topological order
    return ans;
}

int main() {
    int n, m; // n = number of vertices, m = number of edges
    cout << "Enter number of vertices and edges: ";
    cin >> n >> m;

    adj.resize(n);
    cout << "Enter edges (u v):" << endl;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<int> topo_order = topological_sort(n);

    cout << "Topological order: ";
    for (int v : topo_order) {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}