Cod sursa(job #2544903)

Utilizator KPP17Popescu Paul KPP17 Data 12 februarie 2020 17:34:51
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
using namespace std;


#define fisier "sortaret"

#ifdef fisier
    #include <fstream>
    ifstream in(fisier ".in");
    ofstream out(fisier ".out");
#else
    #include <iostream>
    #define in cin
    #define out cout
#endif

#include <algorithm>



const int MAX_N = 50000;

int sol[MAX_N], n, varf;

bool explorat[MAX_N];

#include <vector>
vector<int> de_la[MAX_N];



void add_urmasii_lui(int nod_sursa) {

    explorat[nod_sursa] = true;

    for (
        vector<int>::iterator
        vecin = de_la[nod_sursa].begin();
        vecin != de_la[nod_sursa].end();
        vecin++
    ) {

        //out << "vecin pt "<<nod_sursa<<" -> " << *vecin << endl;

        if (!explorat[*vecin]) {

            add_urmasii_lui(*vecin);

        }

    }

    sol[varf++] = nod_sursa;

    //out << "gata cu " << nod_sursa << endl;

}



int main() {

    int m, x, y;

    in >> n >> m;

    while (m--) {

        in >> x >> y;
        x--, y--;

        de_la[x].push_back(y);

    }

    for (int nod = 0; nod < n; nod++) {

        sort(de_la[nod].begin(), de_la[nod].end());

    }



    for (int nod = 0; nod < n; nod++) {

        if (!explorat[nod]) {

            add_urmasii_lui(nod);

        }

    }



    for (int i = n - 1; i >= 0; i--) {

        out << sol[i] + 1 << ' ';

    }

}













//