Cod sursa(job #613066)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 15 septembrie 2011 15:05:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#define N 50005
struct Nod {
    int x;
    Nod* next;
};
Nod* A[N];
int viz[N];
int sortop[N];
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n, m;
void insert(Nod *& top, int val) {
    Nod* k = new Nod();
    k->x = val;
    k->next = top;
    top = k;
}
void read() {
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        int st, end;
        f >> st >> end;
        insert(A[st], end);
    }
}
void write() {
    for(int i = sortop[0]; i > 0 ; i--)
     g << sortop[i] << " ";

}
void df(int s) {
    viz[s] = 1;
    for(Nod* it = A[s]; it != 0; it = it -> next)
        if(!viz[it -> x])
         df(it -> x);
    sortop[++sortop[0]] = s;
}
void solve() {
    for(int i = 1; i <= n; i++)
     if(!viz[i])
       df(i);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}