Cod sursa(job #1425804)

Utilizator EpictetStamatin Cristian Epictet Data 28 aprilie 2015 00:51:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int N, M, POST_OR[50010];
bool fr[50010];
vector < int > V[50010];

void DFS(int nod)
{
    fr[nod] = 1;
    for (vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); it++) {
        if (!fr[*it]) {
            DFS(*it);
        }
    }

    POST_OR[++POST_OR[0]] = nod;
}

int main()
{
    fin >> N >> M;
    for (int x, y, i = 1; i <= M; i++) {
        fin >> x >> y;
        V[x].push_back(y);
    }

    for (int i = 1; i <= N; i++) {
        if (!fr[i]) {
            DFS(i);
        }
    }

    for (int i = N; i >= 1; i--) {
        fout << POST_OR[i] << ' ';
    }
    fout << '\n';
    fout.close();
    return 0;
}