Mai intai trebuie sa te autentifici.

Cod sursa(job #2912247)

Utilizator tiwerlolPop Iuliu-Daniel tiwerlol Data 7 iulie 2022 16:32:10
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<iomanip>

using namespace std;
ofstream cout("sortaret.out");
ifstream cin("sortaret.in");

vector<vector<int>> v;
vector<int> toposort;
vector<bool> check(300001);

void dfs(int node)
{
    check[node] = 1;
    for(auto x : v[node])
    {
        if(!check[x])
        {
            dfs(x);
        }
    }
    toposort.push_back(node);
}

void solve()
{
    int n, m; cin >> n >> m;

    v = vector<vector<int>> (n+1);

    for(int z = 0; z < m; z++)
    {
        int a, b; cin >> a >> b;
        v[a].push_back(b);
    }

    for(int z = 1; z <= n; z++)
    {
        if(!check[z])
        {
            dfs(z);
        }
    }

    for(vector<int>::reverse_iterator it = toposort.rbegin(); it != toposort.rend(); it++)
    {
        cout << *it << ' ';
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    //int tt;
    ///cin >> tt;
    //while(tt--)
    //{
        solve();
    //}
}