Cod sursa(job #2073441)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 23 noiembrie 2017 10:15:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <vector>
#include <cstdio>
#define N 50005

using namespace std;

int n, m, d[N], sol[N];
vector <int> graf[N];

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int x, y;
        scanf("%d %d\n", &x, &y);
        graf[x].push_back(y);
        d[y]++;
    }
}

void sortare()
{
    for(int i=1;i<=n;i++)
        if(!d[i])
            sol[++sol[0]]=i;
    for(int i=1;i<=n;i++)
    {
        int x=sol[i];
        for(int i=0;i<graf[x].size();i++)
        {
            int nod=graf[x][i];
            d[nod]--;
            if(!d[nod])
                sol[++sol[0]]=nod;
        }
    }
}

void afisare()
{
    for(int i=1;i<=sol[0];i++)
        printf("%d ", sol[i]);
}

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

    citire();
    sortare();
    afisare();
    return 0;
}