// Tri topologique d'un graphe orienté // Version récursive (DFS) // https://www.geeksforgeeks.org/topological-sorting/ #include using namespace std; // Tri topologique par DFS void topologicalSortUtil(int v, vector> &adj, vector &visited, stack &st) { visited[v] = true; // marquer le sommet v comme visité for(int i : adj[v]) // récursion sur les sommets adjacents de v { if(!visited[i]) topologicalSortUtil(i, adj, visited, st); // appel récursif } st.push(v); // ajouter le sommet v sur la pile } // topologicalSortUtil() // Tri topologique vector topologicalSort(vector> &adj) { int V = adj.size(); stack st; // pile pour stocker les sommets vector visited(V, false); // Appel de la fonction récursive à partir de chaque sommet for(int i = 0; i < V; i++) { if(!visited[i]) topologicalSortUtil(i, adj, visited, st); } vector ans; // On ajoute les sommets au vecteur ans while(!st.empty()) { ans.push_back(st.top()); st.pop(); } return ans; } // topologicalSort() int main() { // Graphe représenté sous forme de liste d'adjacences int n = 0, e = 0; cin >> n >> e; // sommets, arcs vector> adj(n); int x = 0, y = 0; for(int k = 0; k < e; k++) { cin >> x >> y; adj[x].push_back(y); } vector ans = topologicalSort(adj); for(auto node: ans) cout << node << ' '; cout << '\n'; return 0; } // main()