Cod sursa(job #311463)

Utilizator sandyxpSanduleac Dan sandyxp Data 3 mai 2009 15:24:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <stack>
using namespace std;

#define NUME "sortaret"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
#define MAXN 50001

int N, M, gradin[MAXN];
int Used[MAXN];
stack<int> C;

struct item { int x; item *r; } *L[MAXN];

void df(int s) {
    Used[s] = 1;
    for (item *p = L[s]; p; p = p->r) {
        if (Used[p->x]) continue;
        df(p->x);
    }
    C.push(s);
}

inline void add(int a, int b) {
    item *p = new item;
    *p = (item) { b, L[a] };
    L[a] = p;
    gradin[b] ++;
}

int main()
{
    fi >> N >> M;
    while (M--) {
        int a, b;
        fi >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= N; ++i)
        if (gradin[i] == 0)
            df(i);
    while (!C.empty()) {
        fo << C.top() << " ";
        C.pop();
    }
    return 0;
}