Cod sursa(job #1200376)

Utilizator armandpredaPreda Armand armandpreda Data 22 iunie 2014 13:13:14
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>
#include <queue>
#define MAX 16001

using namespace std;

vector <int> lista[MAX];
queue <int> q;
int n,m,gr[MAX];
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int i,j,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        lista[x].push_back(y);
        gr[y]++;
    }
    for(i=1;i<=n;++i)
        if(!gr[i])
            q.push(i);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        printf("%d ",x);
        for(i=0;i<lista[x].size();++i)
        {
            gr[lista[x][i]]--;
            if(!gr[lista[x][i]])
                q.push(lista[x][i]);
        }
    }
    return 0;
}