Cod sursa(job #1485965)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 13 septembrie 2015 14:32:31
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#include <stack>

#define MaxN 50005
#define MaxM 100005

using namespace std;

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

stack<int> result;
bool visited[MaxN];
vector<int> G[MaxN];
int N, M, x, y;

void dfs(int n) {
    visited[n] = true;
    for (int neighIndex = 0; neighIndex < G[n].size(); ++neighIndex) {
        int neigh = G[n][neighIndex];
        if (!visited[neigh])
            dfs(neigh);
    }
    result.push(n);
}

int main()
{
    fin >> N >> M;

    for (int m = 1; m <= M; ++m) {
        fin >> x >> y;
        G[x].push_back(y);
    }

    for (int n = 1; n <= N; ++n)
        if (!visited[n])
            dfs(n);

    while (!result.empty()) {
        fout << result.top() << ' ';
        result.pop();
    }

    return 0;
}