Cod sursa(job #2611994)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 7 mai 2020 22:50:47
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

#define MAXN 50100

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

int N, M, deg[MAXN], Q[MAXN];
vector < int > G[MAXN];

void solve () {
    int i, x;
    vector < int > :: iterator it;
    for (x = 1; x <= N; x++) if(deg[x] == 0) Q[++Q[0]] = x;
    for (i = 1; i <= N; i++) {
        x = Q[i];
        for (it = G[x].begin(); it != G[x].end(); ++it) {
            deg[*it] --;
            if (deg[*it] == 0) Q[++Q[0]] = *it;
        }
    }
}

void read () {
    int a, b;
    f >> N >> M;
    for(int i = 1; i <= M; i++) {
        f >> a >> b;
        G[a].push_back (b);
        deg[b] ++;
    }
}

void print () {
    int i;
    for(i = 1; i <= N; i++) g << Q[i] << " ";
}

int main () {
    read();
    solve();
    print();
    return 0;
}