Cod sursa(job #1036733)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 19 noiembrie 2013 16:25:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>
#include <queue>

#define Nmax 50005

using namespace std;

int degree[Nmax],N,M;

vector<int> G[Nmax];
queue<int> Q;

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

void solve()
{
    for(int i = 1; i <= N ; ++i)
        if(degree[i] == 0)
            Q.push(i);
    while(!Q.empty())
    {
        for(vector<int>::iterator it = G[Q.front()].begin();it!= G[Q.front()].end();++it)
        {
            --degree[*it];
            if(degree[*it] == 0)
                Q.push(*it);
        }
        printf("%d ",Q.front());
        Q.pop();
    }
}

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

    read();
    solve();

    return 0;
}