// Tri topologique d'un graphe orienté // Algorithme de Khan (itératif) // https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/ #include using namespace std; // Tri topologique vector topologicalSort(vector> &adj, int V) { vector indegree(V); // degrés entrants de chaque sommet for(int i = 0; i < V; i++) for(auto it : adj[i]) indegree[it]++; queue q; // file pour les sommets de degrés entrants nuls for(int i = 0; i < V; i++) if(indegree[i] == 0) q.push(i); vector result; while(!q.empty()) { int node = q.front(); q.pop(); result.push_back(node); // On décrémente le degré entrant des sommets adjacents au sommet 'node' for(auto it : adj[node]) { indegree[it]--; if(indegree[it] == 0) q.push(it); } } // On vérifie s'il y a un cycle if((int)result.size() != V) { cout << "Le graphe contient un cycle !\n"; return {}; } return result; } // 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); } // Tri topologique vector result = topologicalSort(adj, n); // Affichage des résultats for(auto i : result) cout << i << ' '; cout << '\n'; return 0; } // main()