Cod sursa(job #2211715)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 11 iunie 2018 15:26:31
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>

using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

const int N = 5e4 + 7, M = 1e5 + 7;

int q[N], vf[2 * M], ant[2 * M], sf[N], f[N];
int nl(0);


int x, y;

void adauga() {
    vf[++nl] = y;
    ant[nl] = sf[x];
    sf[x] = nl;
}

void sortaretzbfs(const int& n) {
    int st(0), dr(-1);

    for (int i = 1; i <= n; ++i) {
        if (f[i] == 0) {
            q[++dr] = i;
        }
    }

    while (st <= dr) {
        int x = q[st++];
        int nodc = sf[x];

        cout << x << " ";

        while (nodc != 0) {
            int nod = vf[nodc];
            --f[nod];
            if (f[nod] == 0) {
                q[++dr] = nod;
            }
            nodc = ant[nodc];
        }

    }

    cout << "\n";
}

void dfs(int x, int &top) {
    int nodc = sf[x];

    while (nodc != 0) {
        int nod = vf[nodc];
        dfs(nod, top);
        nodc = ant[nodc];
    }

    q[++top] = x;
}

void sortaretzdfs(const int& n) {
    int top(0);

    for (int i = 1; i <= n; ++i) {
        if (f[i] == 0) {
            dfs(i, top);
        }
    }

    while (top > 0) {
        cout << q[top--] << " ";
    }
    cout << "\n";
}

int main()
{
    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        cin >> x >> y;
        ++f[y];
        adauga();
    }

    sortaretzdfs(n);
//    sortaretzbfs(n);

    return 0;
}