Cod sursa(job #352502)

Utilizator xtremespeedzeal xtreme Data 2 octombrie 2009 08:55:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream.h>
#include <stdio.h>
#include <vector>
#define nmax 50005 
using namespace std;

int n,m,C[nmax],grad[nmax];
vector<int> G[nmax];

void citire()
    {freopen("sortaret.in","r",stdin);
     int i,a,b;scanf("%d %d\n",&n,&m);
     for(i=1;i<=m;i++)
          {scanf("%d %d\n",&a,&b);
           G[a].push_back(b);grad[b]++;
           }
     fclose(stdin);
     }
void sorttop()
     {int i,x;vector<int>::iterator it;
      for(i=1;i<=n;i++)
            if(!grad[i])   C[++C[0]]=i;
      for(i=1;i<=n;i++)
           {x=C[i];
            for(it=G[x].begin();it!=G[x].end();it++)
                         {grad[*it]--;
                          if(!grad[*it])  C[++C[0]]=*it;
                         }
           }
     }  
void scriere()
     {int i;
      freopen("sortaret.out","w",stdout);
      for(i=1;i<=n;i++)  printf("%d ",C[i]);
      printf("\n");
      fclose(stdout);
      }
int main()
    {citire();
     sorttop();
     scriere();
     return 0;
     }