Cod sursa(job #1925570)

Utilizator Mstar_AngelComan Mara Stefania Mstar_Angel Data 13 martie 2017 13:37:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
//sortare topologica
//kahn alghoritm : se aleg vf care nu mai au tati si se pun intr-o lista;
#include<stdio.h>
#include<vector>
#include<stack>
#define N 50001
using namespace std;
vector <int> v[N];
stack <int> stiv;
int dirin[N];
int sol[N];
int n;

void tsort (){
  int i,k,nod;
  for (i=1;i<=n;i++)
    if (dirin[i] == 0)
      stiv.push(i);

  k = 0;
  while (stiv.empty() == 0){
      nod = stiv.top();
      stiv.pop();
      sol[++k] = nod;
      for (i=0;i<v[nod].size();i++){
        dirin[v[nod][i]] --;
        if (dirin[v[nod][i]] == 0)
          stiv.push(v[nod][i]);
      }
  }
}

int main (){
  FILE *in, *out;
  in = fopen ("sortaret.in","r");
  out = fopen ("sortaret.out","w");
  int m,i,n1,n2;
  fscanf(in,"%d%d",&n,&m);
  for (i=1;i<=m;i++){
    fscanf(in,"%d%d",&n1,&n2);
    v[n1].push_back(n2);
    dirin[n2] ++;
  }

  tsort ();

  for (i=1;i<=n;i++)
    fprintf (out,"%d ",sol[i]);

  fclose (in);
  fclose (out);
  return 0;
}