Cod sursa(job #2968466)

Utilizator armand09Armand Miron armand09 Data 21 ianuarie 2023 09:43:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define FASTIO ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define pii pair<int , int>

const int MOD = 1e9 + 7;
const int MAX = 1e5 +5;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m;
vector<int>g[MAX]; unordered_map<int,bool>vis;
unordered_map<int,bool>based;
vector<int>sol;
void topSort(int node)
{
    vis[node] =1;
    for(int i=0;i<g[node].size();i++)
    {
        if(!vis[g[node][i]]){
            based[g[node][i]] = 1;
            topSort(g[node][i]);
             sol.pb(g[node][i]);
        }
    }
    if(!based[node])
        sol.pb(node);
}
int32_t main()
{
    FASTIO;
    fin>>n>>m;
    int root =0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        g[x].pb(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
            topSort(i);
    }
    reverse(sol.begin(),sol.end());
    for(auto i : sol)
        fout<<i<<' ';
}