Cod sursa(job #1413681)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 2 aprilie 2015 00:34:31
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

FILE *f, *g;

const int nmax = 50005;

vector <int> a[nmax];
int n, m, i, grad[nmax];

void read()
{
    int x, y;
    fscanf(f, "%d%d", &n, &m);
    for (i = 1; i <= m; i++)
    {
        fscanf(f, "%d%d", &x, &y);
        a[x].push_back(y);
        grad[y]++;
    }
}

void solve()
{
    queue <int> q;
    int nc;
    for (i = 1 ; i <= n; i++) if (grad[i] == 0) q.push(i);
    while (!q.empty())
    {
        nc = q.front(); q.pop();
        fprintf(g, "%d ", nc);
        for (vector<int>::iterator it = a[nc].begin(); it != a[nc].end(); ++it)
        {
            grad[*it]--;
            if (!grad[*it]) q.push(*it);
        }
    }
}

int main()
{
    f = fopen("sortaret.in", "r");
    g = fopen("sortaret.out", "w");
    read();
    solve();
    return 0;
}