Cod sursa(job #2922117)

Utilizator Paul_DobrescuPaul Dobrescu Paul_Dobrescu Data 4 septembrie 2022 10:45:59
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

void dfs(int k, vector <bool>& viz, vector <int>& topSort, vector <vector <int>>& graf)
{
    viz[k] = true;
    for(auto it : graf[k])
    {
        if(!viz[it])
        {
            dfs(it, viz, topSort, graf);
        }
    }
    topSort.emplace_back(k);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input", "r", stdin);
	freopen("output", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
	vector <vector <int>> graf(n + 1, vector <int> ());
    vector <int> topSort;
    vector <bool> viz(n + 1);
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        graf[x].emplace_back(y);
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!viz[i])
        {
            dfs(i, viz, topSort, graf);
        }
    }
    for(int i = n - 1; i >= 0; --i)
    {
        cout << topSort[i] << " ";
    }
	return 0;
}