Cod sursa(job #781362)

Utilizator visanrVisan Radu visanr Data 24 august 2012 11:57:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

#define pb push_back
#define nmax 50010

int N, M, deg[nmax], Q[nmax], X, Y;
vector<int> G[nmax];

void TopSort()
{
     int i;
     vector<int> :: iterator it;
     for(i = 1; i <= N; i++)
           if(deg[i] == 0)
                     Q[++Q[0]] = i;
     for(i = 1; i <= N; i++)
     {
           int aux = Q[i];
           for(it = G[aux].begin(); it != G[aux].end(); ++it)
           {
                  deg[*it] --;
                  if(deg[*it] == 0) Q[++Q[0]] = *it;
           }
     }
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(; M; M --)
    {
          scanf("%i %i", &X, &Y);
          G[X].push_back(Y);
          deg[Y] ++;
    }
    TopSort();
    for(i = 1; i <= N; i++) printf("%i ", Q[i]);
    return 0;
}