Cod sursa(job #1835752)

Utilizator satzaFoldesi Richard satza Data 27 decembrie 2016 13:31:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct vertex{
    int key;
    struct vertex *next;
}*L[50002],*p,*sol,*q;


int n,m,viz[50002];

void olvas(){
    int i,x,y;
    in >> n >> m;
    for(i = 1; i <= m; ++i){
        in >> x >> y;
        p = new vertex;
        p -> key = y;
        p -> next = L[x];
        L[x] = p;
    }

    /*for(i = 1; i <= n; ++i){
        p = L[i];
        out << i << ": ";
        while(p != NULL){
            out << p -> key << " ";
            p = p -> next;
        }
        out << "\n";
    }*/
}

void df(int nod){
    int i,k;
    viz[nod] = 1;
    struct vertex *p;
    p = L[nod];
    while(p != NULL){
        k = p -> key;
        if(viz[k] == 0) df(k);
        if(p != NULL) p = p -> next;
    }
    q = new vertex;
    q -> key = nod;
    q -> next = sol;
    sol = q;
}

int main()
{
    int i;
    olvas();
    for(i = 1; i <= n; ++i) if(viz[i] == 0) df(i);
    q = sol;
    while(q != NULL){
        out << q -> key << " ";
        q = q -> next;
    }
    return 0;
}