Cod sursa(job #755281)

Utilizator adalLica Adela adal Data 5 iunie 2012 10:00:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <vector>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define pb push_back

using namespace std;
vector< int > G[50005];
queue <int > Q;
vector <int> :: iterator it;
int N, M, i, x, y, deg[50005] ;
bool U[50005];

void load(){
   scanf("%d %d\n", &N, &M);
   for (i=1; i<= M; i++){
     scanf("%d %d\n",&x, &y);
     G[x].pb(y);
     deg[y]++;
  }
}

void sort_BF() {
    vector<int>:: iterator it;

 int i, x;

 for (i = 1; i <= N; i++)
  if (deg[i] == 0){
     Q.push(i);
     U[i]=true;
  }

while (!Q.empty())
{
  x=Q.front();
  printf("%d ", x);
  for(it=G[x].begin(); it!= G[x].end(); it++){
     deg[*it]--;
     if (!U[*it] && deg[*it] == 0){
     Q.push(*it);
     U[*it] = true;
    }
  }
  Q.pop();
 }
}

int main(){
 freopen("sortaret.in","r",stdin);
 freopen("sortaret.out","w",stdout);
 load();
 memset(U, false, sizeof(U));
 sort_BF();
printf("\n");
}