Cod sursa(job #613076)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 15 septembrie 2011 16:35:22
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
//CU STL
#include <fstream>
#define N 50005
#include <vector.h>

using namespace std;

vector< vector<int> > v(N);
int viz[N];
int sortop[N];

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n, m;
void read() {
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        int st, end;
        f >> st >> end;
        v[st].push_back(end);
    }
}
void write() {
    for(int i = sortop[0]; i > 0 ; i--)
     g << sortop[i] << " ";

}
void df(int s) {
    viz[s] = 1;
    for(int it = 0; it < v[s].size(); it++)
        if(!viz[v[s][it]])
         df(v[s][it]);
    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;
}