Cod sursa(job #1846989)

Utilizator danyvsDan Castan danyvs Data 14 ianuarie 2017 11:03:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 50001;

int n, m;
vector < vector < int > > graph(NMAX);
bool seen[NMAX];
stack < int > S;

void read()
{
    int i, x, y;
    fin >> n >> m;
    for (i = 1; i <= m; ++ i)
        {
         fin >> x >> y;
         graph[x].push_back(y);
        }
}

void dfs(int node)
{
    vector < int > :: iterator it;
    seen[node] = true;
    for (it = graph[node].begin(); it != graph[node].end(); ++ it)
        if (!seen[*it])
            dfs(*it);
    S.push(node);
}

void topological_sort()
{
    int i;
    for (i = 1; i <= n; ++ i)
        if (!seen[i])
            dfs(i);
}

void print()
{
    while (!S.empty())
        {
         fout << S.top() << " ";
         S.pop();
        }
    fout << "\n";
}

int main()
{
    read();
    fin.close();
    topological_sort();
    print();
    fout.close();
    return 0;
}