Cod sursa(job #2541652)

Utilizator KPP17Popescu Paul KPP17 Data 8 februarie 2020 17:57:40
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <vector>
using namespace std;



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



const int
MAX_N = 50000,
MAX_M = 100000;

vector<int> inainte[MAX_N], din_generatia[MAX_N];

int n, m, i, j, generatia_lui[MAX_N];



int main() {

    int gen_max, gen;



    in >> n >> m;



    for (gen = 0; gen < n; gen++) {

        generatia_lui[gen] = -1;

    }



    while (m--) {

        in >> i >> j; i--, j--;

        inainte[j].push_back(i);

        gen_max = -1;

        for (vector<int>::iterator k = inainte[i].begin(); k != inainte[i].end(); k++) {

            gen_max = max(gen_max, generatia_lui[*k]);

        }

        if (generatia_lui[i] == -1) {

            generatia_lui[i] = gen_max + 1;
            din_generatia[gen_max + 1].push_back(i);

        }

        if (generatia_lui[j] == -1) {

            generatia_lui[j] = generatia_lui[i] + 1;
            din_generatia[generatia_lui[i] + 1].push_back(j);

        }

    }



    for (gen = 0; gen < n; gen++) {

        for (vector<int>::iterator k = din_generatia[gen].begin(); k != din_generatia[gen].end(); k++) {

            out << *k + 1 << ' ';

        }

    }

}























//