Cod sursa(job #626330)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 26 octombrie 2011 20:56:30
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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],viz[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 k,j,aux;
   FILE *fout=fopen("sortaret.out","w");
   for(i=0;i<n;i++){
      //mai am de afisat n-i noduri
      for(j=0;j<n;j++){//as afisa nodul  j... e ok daca are gradul 0 si nu l-am afisat deja
        if(grad[j]==0 && viz[j]==0){
           viz[j]=1;
           fprintf(fout,"%d ",j+1);
           //scot nodul j (scad cu 1 gradele interioare ale tuturor nodurilor vecine cu j)
           for(k=0;k<lista[j].size();k++)
             grad[lista[j][k]]--;
          break;//am eliminat un nod....ies si mai caut
        }
          
      }
}
  fprintf(fout,"\n");
  fclose(fout);
return 0;
}