Cod sursa(job #489206)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 1 octombrie 2010 19:07:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 50010
#define pb push_back

using namespace std;

vector <int> G[MAX];
int deg[MAX], N, M;

void read()
{
    int a,b ;
    scanf("%d %d",&N,&M);
    for(int i = 1; i <= M; i++)
    {
        scanf("%d %d",&a,&b);
        deg[b]++;
        G[a].pb(b);
    }
}

void solve()
{
    queue <int> Q;
    vector <int>::iterator j;
    for(int i = 1; i <= N; i++)
        if(!deg[i])
            Q.push(i);

    for(int i = 1; i <= N; i++)
    {
        for(j = G[Q.front()].begin(); j < G[Q.front()].end(); j++)
        {
            deg [*j]--;
            if(!deg[*j])
                Q.push(*j);
        }
        printf("%d ", Q.front());
        Q.pop();
    }
}

int main()
{
    freopen ("sortaret.in","r",stdin);
    freopen ("sortaret.out","w",stdout);

    read();
    solve();
    return 0;
}