Cod sursa(job #626319)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 26 octombrie 2011 20:35:06
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 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];//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].push_back(b);
      grad[b]++;
   }
   //incep parcurgerea...O(n^2);
   int j,aux;
   FILE *fout=fopen("sortaret.out","w");
   for(i=0;i<n;i++){
      //pt nodul i, gradul sau interior este grad[i]; este el 0?
      if(grad[i]==0){
          fprintf(fout,"%d ",i+1);
          //scot nodul i (scad cu 1 gradele interioare ale tuturor nodurilor vecine cu i)
          for(j=0;j<lista[i].size();j++)
            if(grad[lista[i][j]]!=0)grad[lista[i][j]]--;//daca e 0, inseamna ca l-am scos deja
          
      }
}

return 0;
}