Cod sursa(job #2204068)

Utilizator dobrandreiAndrei Dobra dobrandrei Data 14 mai 2018 12:44:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <deque>
using namespace std;
FILE *f,*g;

int n,m;
int start[50002],t[2][100002],leg[50002];

deque <int> deq;

void read()
{
  fscanf(f,"%d %d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int x,y;
    fscanf(f,"%d %d",&x,&y);
    t[0][i]=y;
    t[1][i]=start[x];
    start[x]=i;
    leg[y]++;
  }
}

void top_sort()
{
  for(int i=1;i<=n;i++)
    if(leg[i]==0)
      deq.push_back(i);

  while(!deq.empty())
  {
    int node=deq.front();
    int poz=start[node];

    fprintf(g,"%d ",node);

    while(poz)
    {
      int new_node=t[0][poz];
      leg[new_node]--;
      if(!leg[new_node])
        deq.push_back(new_node);

      poz=t[1][poz];
    }
    deq.pop_front();
  }
}

int main()
{
    f=fopen("sortaret.in","r");
    g=fopen("sortaret.out","w");
    read();
    top_sort();
    return 0;
}