Cod sursa(job #2795682)

Utilizator rimihaiMihai Radu-Ioan rimihai Data 6 noiembrie 2021 19:37:12
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

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


vector<int> lista_adiacenta[100001];
unordered_map<int,bool> vector_vizitat;
deque<int> lista_sorttop;

void adaugare_muchie_orientata(vector<int> lista_adiacenta[], int u, int v)
{
    lista_adiacenta[u].push_back(v);
}

void sortare_topologica(int x)
{
    vector_vizitat[x]=1;
    for(int i : lista_adiacenta[x])
    {
        if(vector_vizitat[i]==0)
            sortare_topologica(i);
    }
    lista_sorttop.push_front(x);
}

int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        fin>>a>>b;
        adaugare_muchie_orientata(lista_adiacenta,a,b);
    }
    for(int i=n; i>=1; i--)
    {
        if(vector_vizitat[i]==0)
            sortare_topologica(i);
    }
    while(!lista_sorttop.empty())
        {
            int x=lista_sorttop.front();
            fout<<x<<" ";
            lista_sorttop.pop_front();
        }
    return 0;
}