Cod sursa(job #1226376)

Utilizator MaarcellKurt Godel Maarcell Data 5 septembrie 2014 12:30:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

int N,M,indeg[50100],q[50100],K,a[50100]; vector<int> graf[50100];

void toposort(void){
    int i,l=1;
    while (l<=N){
        a[l]=q[l];
        for (i=0; i<graf[q[l]].size(); i++){
            indeg[graf[q[l]][i]]--;
            if (!indeg[graf[q[l]][i]])
                q[++K]=graf[q[l]][i];
        }
        l++;
    }
}

int main(){
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    in >> N >> M;

    int i,x,y;
    for (i=0; i<M; i++){
        in >> x >> y;
        graf[x].push_back(y);
        indeg[y]++;
    }

    for (i=1; i<=N; i++)
        if (!indeg[i])
            q[++K]=i;
    toposort();

    for (i=1; i<=N; i++)
        out << a[i] << " ";


    return 0;
}