Cod sursa(job #1796305)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 3 noiembrie 2016 12:17:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>

using namespace std;

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

void DFS(int x);

bool uz[50005];
vector<int> auxx;
vector< vector<int> > L;
int nr, n, m, gr[50005], o[50005];

int main()
{
    int i, x, y;

    fin >> n >> m;
    auxx.push_back(0);
    for (i=0;i<=n;i++)
        L.push_back(auxx);
    for (i=1;i<=m;i++)
    {
        fin >> x >> y;
        gr[y]++;
        L[x][0]++;
        L[x].push_back(y);
    }
    for (i=1;i<=n;i++)
        if (gr[i] == 0)
        {
            DFS(i);
            break;
        }
    for (i=n;i>=1;i--)
        fout << o[i] << ' ';
    fout << '\n';
    return 0;
}

void DFS(int x)
{
    int i;

    uz[x] = 1;
    for (i=1;i<=L[x][0];i++)
        DFS(L[x][i]);
    o[++nr] = x;
}