Cod sursa(job #2205176)

Utilizator herbertoHerbert Mohanu herberto Data 18 mai 2018 10:01:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<bits/stdc++.h>
using namespace std;
#define MAXM 100001
#define MAXN 50001
vector<int> g[MAXM];
int st, dr;
int nrp[MAXN];
int sol[MAXN], nr=0;
int q[MAXM];

inline void bfs(){
  int x, y, i;
  while(st<=dr){
    x=q[st];
//    printf("%d %d %d\n", st, dr, q[st]);
    nr++; sol[nr]=x;
    for(i=0; i<g[x].size(); i++){
      y=g[x][i];
      nrp[y]--;
      if(nrp[y]==0)
        dr++, q[dr]=y;
    }

    st++;
  }
}
int main(){
  FILE*fin=fopen("sortaret.in", "r");
  FILE*fout=fopen("sortaret.out", "w");
  int n, m, a, b, i;
  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=m; i++){
    fscanf(fin, "%d%d", &a, &b);
    nrp[b]++;
    g[a].push_back(b);
  }
  st=1;dr=0;
  for(i=1; i<=n; i++)
    if(nrp[i]==0){
      dr++;
      q[dr]=i;
    }
  bfs();
  for(i=1; i<=n; i++)
    fprintf(fout, "%d ", sol[i]);

  return 0;
}