Cod sursa(job #2254662)

Utilizator HerddexJinga Tudor Herddex Data 5 octombrie 2018 18:30:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct Node
{
    int node;
    Node* next;
} *G[50001];

bool eVizitat[50001];
Node *lista;

void dfs(int v)
{
    eVizitat[v] = true;
    for(Node *p= G[v]; p!=0; p = p->next)
        if(!eVizitat[p->node])
            dfs(p->node);

    Node *p = new Node;
    p->node = v;
    p->next = lista;
    lista = p;
}

int main()
{
    int N, M;
    fin >> N >> M;

    while(M)
    {
        int v, w;
        fin >> v >> w;

        Node *p = new Node;
        p -> node = w;
        p -> next = G[v];
        G[v] = p;
        M--;
    }

    for(int v=1; v<=N; v++)
        if(!eVizitat[v])
            dfs(v);

    for(Node *p = lista; p!=0; p = p->next)
    {
        fout << p->node << ' ';
    }

    fin.close();
    fout.close();
    return 0;
}