Cod sursa(job #3198034)

Utilizator satzaFoldesi Richard satza Data 28 ianuarie 2024 10:21:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
///topological sort based on indegree of vertex
///perform a bfs, insert to the Q every vertex with indegree 0
///while Q is not empty, extract the front vertex x, add x to solution and delete all edges (x,y)
///if indegree[y] becames 0 add y to the Q
#include <bits/stdc++.h>

using namespace std;

int N, M, nr;
vector<int>L[50002];///adjacency list
int indegree[50002];///indegree[i] = number of edges starting from i to vertices not inserted in topoSort[]
int vis[50002], topoSort[50002];
queue<int>Q;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

int main(){
    in >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y;
        in >> x >> y;
        L[x].push_back(y);
        indegree[y] = indegree[y] + 1;
    }

    for(int i = 1; i <= N; i++) if(indegree[i] == 0) Q.push(i);///insert all vertices with 0 indegree

    nr = 0;
    while(Q.empty() == false){
        int x = Q.front();
        Q.pop();
        nr = nr + 1;
        topoSort[nr] = x;
        for(int i = 0; i < L[x].size(); i++){
            int j = L[x][i];
            indegree[j] = indegree[j] - 1;///remove edge x --> j
            if(indegree[j] == 0) Q.push(j);///add to queue
        }
    }

    for(int i = 1; i <= N; i++) out << topoSort[i] << " ";
    return 0;
}