Cod sursa(job #3040158)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 29 martie 2023 13:40:28
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAXN 500005
using namespace std;

int frec[MAXN];
vector <int> graf[MAXN];
queue <int> q;

int main(){
  int n,m,i,x,y;
  FILE *fin,*fout;
  fin=fopen("sortaret.in","r");
  fout=fopen("sortaret.out","w");
  fscanf(fin,"%d%d",&n,&m);

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d",&x,&y);
    graf[x].push_back(y);
    frec[y]++;
  }

  for(i=1;i<=n;i++){
    if(frec[i]==0){
      q.push(i);
    }
  }

  while(!q.empty()){
    x=q.front();
    fprintf(fout,"%d ",x);
    q.pop();
    for(int node : graf[x]){
      frec[node]--;
      if(frec[node]==0){
        q.push(node);
      }
    }
  }

  fclose(fin);
  fclose(fout);
  return 0;
}