Cod sursa(job #626345)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 26 octombrie 2011 21:26:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define maxn 50010

vector <int> lista[maxn];//lista[i][] lista vecinilor nodului i
int grad[maxn],coada[maxn];//grad[i]=nr de arce care intra in i

int main(){
   int n,m;
   FILE *fin=fopen("sortaret.in","r");
   fscanf(fin,"%d%d",&n,&m);
   int i,a,b;
   for(i=0;i<m;i++){
      fscanf(fin,"%d%d",&a,&b);
      lista[a-1].push_back(b-1);
      grad[b-1]++;
   }
   //incep parcurgerea...O(n^2);
   int li=0,ls=0;
   FILE *fout=fopen("sortaret.out","w");
   //adaug totate nodurile care initial au gradul exterior 0, in coada
   for(i=0;i<n;i++)
     if(grad[i]==0)coada[ls++]=i;
  //ls++; 
  while(li<ls){
     //iau coada[li] si expandez cu toti vecinii sai care in urma scaderii au grad nul
     for(i=0;i<lista[coada[li]].size();i++){
        grad[lista[coada[li]][i]]--;//scad gradul tuturor vecinilor
        if(grad[lista[coada[li]][i]]==0){
          //daca in urma scaderii sunt grade nule, le adaug in coada
           coada[ls++]=lista[coada[li]][i];
        }
     } 
  li++;
  }
  
  for(i=0;i<n;i++)fprintf(fout,"%d ",coada[i]+1);
          
  fprintf(fout,"\n");
  fclose(fout);
return 0;
}