Cod sursa(job #1354747)

Utilizator XeBluePodaru Mihai XeBlue Data 21 februarie 2015 23:36:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

using namespace std;

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

#define N 50001

struct graf {
    int nod;
    graf *next;} *A[N];

int n, m, a, b, T[N], f;
bool viz[N];

void add(int a, int b)
{
    graf *p = new graf;
    p -> nod = b;
    p -> next = A[a];
    A[a] = p;
}

void citire()
{
    in >> n >> m;

    for(int i=1;i<=m;i++)
        in >> a >> b, add(a, b);
}

void dfs(int i)
{
    viz[i] = 1;
    for(graf *p=A[i]; p; p = p->next)
        if(!viz[p->nod])
            dfs(p->nod);
    T[++f] = i;
}

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

void afisare()
{
    for(int i=n; i; i--)
        out << T[i] << " ";
}

int main()
{
    citire();
    ST();
    afisare();

    in.close();
    out.close();
    return 0;
}