1int n; // number of vertices
2vector<vector<int>> adj; // adjacency list of graph
3vector<bool> visited;
4vector<int> ans;
5
6void dfs(int v) {
7 visited[v] = true;
8 for (int u : adj[v]) {
9 if (!visited[u])
10 dfs(u);
11 }
12 ans.push_back(v);
13}
14
15void topological_sort() {
16 visited.assign(n, false);
17 ans.clear();
18 for (int i = 0; i < n; ++i) {
19 if (!visited[i])
20 dfs(i);
21 }
22 reverse(ans.begin(), ans.end());
23}
24
1//Topological sort DFS
2//Complete code
3//Possible Only on DAG(Directed Acyclic Graph)
4#include<bits/stdc++.h>
5using namespace std;
6void addedge(vector<int>adj[],int u,int v)
7{
8 adj[u].push_back(v);
9
10}
11void topo(int val,stack<int>&st,vector<int>adj[],vector<int>&visited)
12{
13 visited[val]=1;
14 for(auto i:adj[val])
15 {
16 if(!visited[i])
17 {
18 topo(i,st,adj,visited);
19 }
20 }
21 st.push(val);
22}
23void toposort(vector<int>adj[],int n)
24{
25 stack<int>st;
26 vector<int>visited(n,0);
27 for(int i=0;i<n;i++)
28 {
29 if(visited[i]==0)
30 {
31 topo(i,st,adj,visited);
32 }
33 }
34 vector<int>topo;
35 while(!st.empty())
36 {
37 topo.push_back(st.top());
38 st.pop();
39 }
40 int s=topo.size();
41 for(int j=0;j<s;j++)
42 {
43 cout<<topo[j]<<" ";
44 }
45}
46int main()
47{
48 int vertex,edges;
49 cout<<"Enter the vertex and edges"<<endl;
50 cin>>vertex>>edges;
51 vector<int>adj[vertex];
52 int a,b;
53 cout<<"Enter the links"<<endl;
54 for(int i=0;i<vertex;i++)
55 {
56 cin>>a>>b;
57 addedge(adj,a,b);
58 }
59 toposort(adj,vertex);
60 return 0;
61}
62