Cod sursa(job #2485252)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 1 noiembrie 2019 10:56:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=50005;
vector <int> gr[N];
int q[N];
int prv[N];
FILE*fin,*fout;
void bfs(int n){
  int st=0,dr=-1;
  for(int i=1;i<=n;i++){
    if(prv[i]==0){
      q[++dr]=i;
    }
  }
  while(st<=dr){
    int x=q[st++];
    fprintf(fout,"%d ",x);
    for(int i=0;i<gr[x].size();i++){
      prv[gr[x][i]]--;
      if(prv[gr[x][i]]==0)
        q[++dr]=gr[x][i];
    }
  }
}
int main()
{
  fin=fopen("sortaret.in","r");
  fout=fopen("sortaret.out","w");
  int n,m;
  fscanf(fin,"%d%d",&n,&m);
  for(int i=1;i<=m;i++){
    int x,y;
    fscanf(fin,"%d%d",&x,&y);
    gr[x].push_back(y);
    prv[y]++;
  }
  bfs(n);
  return 0;
}