Cod sursa(job #2760152)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 23 iunie 2021 13:42:05
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
#define nmax 50001
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> parintii(nmax,0);
vector<int> graf[nmax];
vector<bool> viz(nmax,0);
queue<int> q;
void dfs(){
    while(!q.empty()){
        int n=q.front();
        q.pop();
        if(viz[n])continue;
        out<<n<<' ';
        viz[n]=1;
        for(auto i:graf[n]){
            if(!(--parintii[i]))q.push(i);
        }
    }
}
int main(){
    int n,m;
    in>>n>>m;
    for(;m;m--){
        int i,j;
        in>>i>>j;
        graf[i].push_back(j);
        parintii[j]++;
    }
    for(int i=1;i<=n;i++){
        if(!parintii[i])q.push(i);
    }
    dfs();
}