Cod sursa(job #2054843)

Utilizator ioana_marinescuMarinescu Ioana ioana_marinescu Data 2 noiembrie 2017 16:43:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
const int NMAX = 50005;
using namespace std;

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

int N, M, grade[NMAX], coada[NMAX];
vector<int>G[NMAX];

int main() {
    int i, x, a, b;
    vector<int>:: iterator it;
    fin>>N>>M;
    for(i=1; i<=M; i++) {
        fin>>a>>b;
        G[a].push_back(b);
        grade[b]++;
    }
    for(i=1; i<=N; i++) {
        if(grade[i]==0)
            coada[++coada[0]]=i;
    }
    for(i=1; i<=N; i++) {
        x=coada[i];
        for(it=G[x].begin(); it!=G[x].end(); ++it) {
            grade[*it]--;
            if(grade[*it]==0)
                coada[++coada[0]]=*it;
        }
    }
    for(i=1; i<=N; i++)
        fout<<coada[i]<<" ";
    return 0;
}