Cod sursa(job #1131556)

Utilizator Theorytheo .c Theory Data 28 februarie 2014 21:34:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

const int NMAX = 50009;

int N; int M; bool viz[NMAX];

vector<int> G[NMAX], Solution;

void DFS(const int &nod) {

    viz[nod] = true;
    for(unsigned i = 0 ;i < G[nod].size(); ++i)
        if(viz[G[nod][i]] == false)
            DFS(G[nod][i]);

    Solution.push_back(nod);

}

int main() {

    fin >> N >> M;

    for(int i = 1; i <= M; ++i) {
        int A; int B; fin >> A >> B;
        G[A].push_back(B);
    }

    for(int i = 1; i <= N; ++i)
        if(viz[i] == false)
            DFS(i);

    reverse(Solution.begin(), Solution.end());

    for(unsigned i = 0 ;i < Solution.size(); ++i)
        fout << Solution[i] <<" ";

    return 0;
}