Cod sursa(job #292883)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 31 martie 2009 19:24:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <algorithm>
#include <queue>

#define FIN "sortaret.in"
#define FOUT "sortaret.out"

#define N 500010

using namespace std;

int n, m;
char x[N];

pair <int, int> d[N];

vector <int> v[N];

queue <int> q;

void read()
{
    int i, x, y;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d", &n, &m);

    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);

        ++d[x].first;
        ++d[y].second;

        v[x].push_back(y);
    }
}

void solve()
{
    int p, i;

    for (i = 1; i <= n; ++i)
        if (!d[i].second)
        {
            q.push(i);
            x[i] = 1;
        }
    while (!q.empty())
    {
        p = q.front();

        printf("%d ", p);

        q.pop();

        for (i = 0; i < d[p].first; ++i)
            if (!x[v[p][i]])
            {
                -- d[v[p][i]].second;
                if (d[v[p][i]].second == 0)
                {
                    q.push(v[p][i]);
                    x[v[p][i]] = 1;
                }
            }
    }
}

int main()
{
    read();

    solve();

    printf("\n");
}