Cod sursa(job #599534)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 29 iunie 2011 00:22:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#define nmax 50001
using namespace std;

int n, m, nr = 0;
unsigned short a[nmax][30];
bool viz[nmax];
int p[nmax];

void citire(){
    unsigned short x,y;
    ifstream in("sortaret.in");
    in >> n >> m;
    for(int i=1;i<=n;++i) a[i][0] = 0;
    for(;m--;){
        in >> x >> y;
        ++a[x][0];a[x][a[x][0]] = y;
    }
    in.close();
}

void dfs(int x){
    viz[x] = 1;
    for(int i=1;i<=a[x][0];++i)
        if(!viz[a[x][i]]) dfs(a[x][i]);
    p[nr++] = x;
}

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

void afis(){
    ofstream out("sortaret.out");
    for(;nr--;)
        out << p[nr] << " ";
    out.close();
}

int main()
{
    citire();
    rezolv();
    afis();
    return 0;
}