Cod sursa(job #2645987)

Utilizator OvidRata Ovidiu Ovid Data 30 august 2020 12:32:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

ifstream fin("sortaret.in"); ofstream fout("sortaret.out");
#define cin fin
#define cout fout

int t, n, m, k, a[300010], b[300010], q, l, r;
vector<int> g[50010];
int cnt[50010];
bool v[50010];


int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=m; i++){
    int u, v; cin>>u>>v;
    g[u].pb(v); cnt[v]++;
}
queue<int> q;
int frst=1;
for(int i=1; i<=n; i++){
    if(cnt[i]==0){
        q.push(i);
    }
}
if(q.empty()){
    q.push(frst);
}

vector<int> res;

while(!q.empty()){
    int f=q.front(); q.pop(); v[f]=true;
    for(int i:g[f]){
        if(!v[i]){
            cnt[i]--;
            if(cnt[i]==0){
                q.push(i);
            }
        }
    }
    res.pb(f);
}
for(int i=0; i<res.size(); i++){
    cout<<res[i]<<" ";
}


return 0;
}