Cod sursa(job #2538223)

Utilizator sipdavSipos David Oliver sipdav Data 4 februarie 2020 16:04:04
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

const int dim = 50001;

struct nod
{
    int x;
    nod* urm;
};

nod* e[dim];
nod* l;
int n, m, viz[dim];

void adauga(int x, int y)
{
    nod* n = new nod;
    n->x = y;
    n->urm = e[x];
    e[x] = n;
}

void read()
{
    int x, y;
    in>>n>>m;
    for(int i = 1;i <= m;i++)
    {
        in>>x>>y;
        adauga(x, y);
    }
}

void addtorez(int k)
{
    nod* n = new nod;
    n->x = k;
    n->urm = l;
    l = n;
}

void dfs(int k)
{
    if(viz[k])
        return;
    viz[k] = 1;
    for(nod *p = e[k];p != NULL;p = p->urm)
    {
        if(!viz[p->x])
            dfs(p->x);
    }
    addtorez(k);
    viz[k] = 2;
}

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

void print()
{
    for(nod* p = l;p != NULL;p = p->urm)
        out<<p->x<<' ';
}

int main()
{
    read();
    solve();
    print();
    return 0;
}