Cod sursa(job #3001003)

Utilizator SamurayxJackDiaconescu Octavian SamurayxJack Data 13 martie 2023 09:46:08
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include<bits/stdc++.h>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int MAXI=1e4*5+1;

int n,grad[MAXI];
vector<int>G[MAXI];
vector<int>H;
queue<int>Q;

void read(){
 int m,x,y;
 fin>>n>>m;
 for(int i=0;i<m;i++){
    fin>>x>>y;
    G[x].push_back(y);
    grad[y]++;
 }

}

void sorttop(){
for(int i=1;i<=n;i++) if(!grad[i]) Q.push(i);
while(!Q.empty()){
    int nod=Q.front();
    Q.pop();
    H.push_back(nod);
    for(auto v:G[nod])
        if(--grad[v]==0) Q.push(v);
}

}


int main(){
    read();
    sorttop();
    for(auto v:H) fout<<v<<" ";
    return 0;
}