Cod sursa(job #1317404)

Utilizator retrogradLucian Bicsi retrograd Data 14 ianuarie 2015 21:18:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<vector>

#define MAXN 50001

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int> G[MAXN];
int SOL[MAXN], s, e;
int GRADI[MAXN];
int n, m;

int main() {
    fin>>n>>m;
    int a, b;
    while(m--) {
        fin>>a>>b;
        G[a].push_back(b);
        GRADI[b] ++;
    }
    for(int i=1; i<=n; i++) {
        if(GRADI[i] == 0) {
            SOL[++e] = i;
        }
    }
    s = 1;
    while(s <= e) {
        for(vector<int>::iterator it = G[s].begin(); it!=G[s].end(); ++it) {
            GRADI[*it]--;
            if(!GRADI[*it])
                SOL[++e] = *it;
        }
        s++;
    }

    for(int i=1; i<=n; i++) {
        fout<<SOL[i]<<" ";
    }
}