Cod sursa(job #2029887)

Utilizator osiaccrCristian Osiac osiaccr Data 30 septembrie 2017 16:27:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#define DEF 50001

using namespace std;

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

vector <int> N[DEF];

int n, m, sol[DEF], k;
short v[DEF];
bool viz[DEF];

void add_arc (int x, int y) {
    for (int i = 0; i < N[x].size (); i++) {
        if (N[x][i] == y)
            return;
    }
    N[x].push_back (y);
    v[x] = -1;
    if (v[y] < 0)
        v[y] = 1;
    else
        v[y]++;
}

void bfs (int nod) {
    int c[DEF], p = 1, u = 0;
    viz[0] = 1;
    c[++u] = 0;
    while (p <= u) {
        if (v[c[p]] <= 0)
            sol[++k] = c[p];
        for (int i = 0; i < N[c[p]].size (); i++) {
            int vecin = N[c[p]][i];
            if (viz[vecin] == 0) {
                c[++u] = vecin;
                if (v[vecin] > 0)
                    v[vecin]--;
                else
                    viz[vecin] = 1;
            }
        }
        p++;
    }
}

int main () {
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;
        add_arc (x, y);
    }

    for (int i = 1; i <= n; i++) {
        if (v[i] == -1)
            N[0].push_back (i);
    }

    bfs (0);

    for (int i = 1; i <= k - 1; i++)
        fout << sol[i + 1] << " ";

    return 0;
}