Cod sursa(job #913173)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 13 martie 2013 10:09:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int n, m;
bool edge[5005][5005];
vector<int> lista(0);
queue<int> set;
int main()
{
    int i, j;
    int x, y;
    int node, ok;
    freopen("sortaret.in", "r", stdin);
    freopen("Sortaret.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        edge[x][y] = 1;
    }
    for (i = 1; i <= n; i++)
    {
        ok = 1;
        for (j = 1; j <= n; j++)
            if (edge[j][i])
            {
                ok = 0;
                break;
            }
        if (ok)
            set.push(i);
    }

    while (!set.empty())
    {
        node = set.front();
        set.pop();

        lista.push_back(node);
        for (i = 1; i <= n; i++)
            if (edge[node][i])
            {
                edge[node][i] = 0;
                ok = 1;
                for (j = 1; j <= n; j++)
                    if (edge[j][i])
                    {
                        ok = 0;
                        break;
                    }
                if (ok)
                    set.push(i);
            }
    }

    for (i = 0; i < lista.size(); i++)
        printf("%d ", lista[i]);
    printf("\n");
    return 0;
}