Cod sursa(job #2199118)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 26 aprilie 2018 18:10:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
#define dimn 50005

std::ifstream f("sortaret.in");
std::ofstream g("sortaret.out");

int N, M;
std::list <int> adj[dimn];
int gre[dimn];
int ns, sol[dimn];

void sort() {
    for (int i=0; i<N; i++)
        if(!gre[i+1]) sol[ns++] = i+1;

    for (int i=0, x; i<N; i++) {
        x = i+1;
        for(auto vec:adj[x]) {
            gre[vec]--;
            if(!gre[vec]) sol[ns++] = vec;
        }
    }
}

void citire() {
    f >> N >> M;
    for (int i=0, x, y; i<M; i++) {
        f >> x >> y;
        adj[x].push_back(y);
        gre[y]++;
    }
}
void rezolvare() {
    sort();
    for (int i=0; i<N; i++)
        g << sol[i] << " " ;
}

int main()
{
    citire();
    rezolvare();

    return 0;
}