Cod sursa(job #1613084)

Utilizator PhilipDumitruPhilip Dumitru PhilipDumitru Data 25 februarie 2016 10:41:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

vector<int> adiacList[50001];
int n;
stack<int> orderStack;
bool visited[50001];

void topologicSort(int i)
{
    visited[i] = true;
    vector<int>::iterator it, it_end;
    it = adiacList[i].begin();
    it_end = adiacList[i].end();
    for (; it != it_end; ++it)
    {
        if (!visited[*it])
        topologicSort(*it);
    }
    orderStack.push(i);
}

int main()
{
    FILE * fin = fopen("sortaret.in", "r");
    FILE * fout = fopen("sortaret.out", "w");

    int m;
    fscanf(fin, "%d %d", &n, &m);

    int x, y;
    while(m--)
    {
        fscanf(fin, "%d %d", &x, &y);
        adiacList[x].push_back(y);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!visited[i])
        {
            topologicSort(i);
        }
    }
    while (!orderStack.empty())
    {
        fprintf(fout, "%d ", orderStack.top());
        orderStack.pop();
    }
    fprintf(fout, "\n");

    fclose(fin);
    fclose(fout);
    return 0;
}