Cod sursa(job #1532272)

Utilizator zertixMaradin Octavian zertix Data 21 noiembrie 2015 15:17:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <cstdio>
#define MAX 50005
#include <vector>
using namespace std;

int n,q[MAX],m,grad[MAX]; ///grad->gradul INTERIOR al nodului, nu cel exterior
vector <int > g[MAX];

void solve()
{
    int x;

    for (x=1;x<=n;++x)
        if (grad[x]==0)
            q[++q[0]]=x;

    for (int i=1;i<=n;++i)
    {
        x=q[i];
        for (vector <int > :: iterator it=g[x].begin();it!=g[x].end();++it)
        {
            --grad[*it];
            if (grad[*it]==0)
                q[++q[0]]=*it;
        }
    }
}

void citesc()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        ++grad[b];
    }
}

void afis()
{
    for (int i=1;i<=n;++i)
        printf("%d ",q[i]);
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    citesc();
    solve();
    afis();
    return 0;
}