Cod sursa(job #1317400)

Utilizator retrogradLucian Bicsi retrograd Data 14 ianuarie 2015 21:16:52
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 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], begin, end;
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[++end] = i;
        }
    }
    begin = 1;
    while(begin <= end) {
        for(vector<int>::iterator it = G[begin].begin(); it!=G[begin].end(); ++it) {
            GRADI[*it]--;
            if(!GRADI[*it])
                SOL[++end] = *it;
        }
        begin++;
    }

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