Cod sursa(job #2370471)

Utilizator andreistanStan Andrei andreistan Data 6 martie 2019 12:19:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
const int MAXN = 50001;

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

nod *v[MAXN];
int N, M, postordine[MAXN], nr;
bool viz[MAXN];

void add(nod *&dest, int x)
{
    nod *p;
    p = new nod;
    p->x = x;
    p->next = dest;
    dest = p;
}

void DFS(int x)
{
    viz[x] = 1;
    for(nod *p = v[x]; p != NULL; p = p->next)
        if(!viz[p->x])
            DFS(p->x);
    postordine[++nr] = x;
}

int main()
{
    f >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        f >> x >> y;
        add(v[x], y);
    }
    for(int i = 1; i <= N; i++)
        if(!viz[i])
            DFS(i);
    ///Ordinea topologica a varfurilor:
    for(int i = N; i > 0; i--)
        g << postordine[i] << ' ';
    return 0;
}