Cod sursa(job #749801)

Utilizator alexalbu95Albu Alexandru alexalbu95 Data 18 mai 2012 20:19:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
// sortare topologica - alocare dinamica
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
const int maxn=50001;
int U[maxn], V[maxn], n, m, i, t;
struct point{
    int info;
    point *urm;
}*G[maxn];

void add(int x, int y)
{
    point *p;
    p=new point;
    p->info=y;
    p->urm=G[x];
    G[x]=p;
}

void citire()
{
    int i, j;
    f>>n>>m;
    for(int k=1; k<=m; ++k)
    {
        f>>i>>j;
        add(i, j);
    }
    m=0;
}

void dfs(int nod)
{
    point *p;

    U[nod] = 1;
    for(p=G[nod]; p!=NULL; p=p->urm)
        if(!U[p->info])
            dfs(p->info);
    V[++m]=nod;
    cout<<m<<" ";
}

int main()
{
    citire();
    for(int k=1; k<=n; ++k) if(!U[k]) dfs(k);
    for(i=m; i>=1; i--) g<<V[i]<<" ";
}