Cod sursa(job #2029856)

Utilizator osiaccrCristian Osiac osiaccr Data 30 septembrie 2017 15:56:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 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;
bool viz[DEF], v[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[y]++;
}

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

    bfs (0);

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

    return 0;
}