Cod sursa(job #2581175)

Utilizator NoodlesAndi Domnulete Noodles Data 14 martie 2020 16:56:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>

using namespace std;

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

    struct Nod{
        int info;
        Nod * next;
    };

    int viz[100005], n, m, x, y, i;
    Nod listadeAdiacenta[100005];
    int control[100005];


    void adaugare(Nod * prim, int z){
        Nod * newNode = new Nod;
        newNode -> info = z;
        newNode -> next = NULL;
        Nod * it = prim;
        while(it -> next != NULL){
            it = it-> next;
        }
        it -> next = newNode;
    }

    int t = 1;

    void dfs(int plecare){
        if(viz[plecare] == 1){
            return;
        }


        viz[plecare] = 0;

        Nod * it = listadeAdiacenta[plecare].next;

        while(it != NULL){
            dfs(it -> info);
            it = it -> next;
        }

        control[t] = plecare;
        t++;
        viz[plecare] = 1;
    }


int main()
{
    f >> n >> m;

    for(i = 1; i <= n; i++){
        viz[i] = 0;
    }

    for(i = 1; i <= m; i++){
        f >> x >> y;

        Nod * listaX = &listadeAdiacenta[x];
        adaugare(listaX, y);
    }

    for(i = 1; i <= n; i++){
        if(viz[i] == 0){
            dfs(i);
        }
    }

    for(i = n; i >= 1; i--){
        f2 << control[i] << " ";
    }

    return 0;
}