Cod sursa(job #2879724)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 28 martie 2022 22:07:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

void dfs(vector <vector<int>> & vecini, vector<bool> & viz, vector <int> & rez, int start)
{
    for (auto i : vecini[start])
        if (viz[i-1])
            return;
        else
        {
            viz[i-1] = 1;
            dfs(vecini, viz, rez, i-1);
        }
    rez.push_back(start+1);

}
int noduri, muchii, i, j;

int main()
{
    fin >> noduri >> muchii;
    vector <vector<int>> vecini;
    vecini.assign(noduri, {});
    while (muchii)
    {
        fin >> i >> j;
        vecini[i-1].push_back(j);
        muchii--;
    }
    for (i = 0; i <noduri; i++)
    {
        if (vecini[i].size())
        {
            sort(vecini[i].begin(), vecini[i].end());
            for (auto j = vecini[i].end()-1; j > vecini[i].begin(); j--)
                if (*j == *(j-1))
                    vecini[i].erase(j);
        }
    }
/*
    for (i = 0; i <noduri; i++)
    {
        fout << i + 1 << ' ';
        for (auto j : vecini[i])
            fout << j << ' ';
        fout <<'\n';
    }*/
    vector <bool> viz(noduri, 0);
    vector <int> rez;
    for (i = 0; i < noduri; i++)
    {
        if (viz[i] == 0)
            dfs(vecini, viz, rez, i);
    }
    for (auto i = noduri-1; i >= 0; i--)
        fout << rez[i] << ' ';
    return 0;
}