Cod sursa(job #2199126)

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

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

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

void citire() {
    f >> N >> M;
    for(int i=1, y, x; i<=M; i++) {
        f >> x >> y;
        adj[x].push_back(y);
        gre[y]++;
    }
}
void rezolvare() {
    for (int i=1; i<=N; i++)
        if (!gre[i]) sol[ns++] = i;

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

    for (int i=0; i<N; i++)
        g << sol[i] << " ";
    g << "\n";
}

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

    return 0;
}