Cod sursa(job #590572)

Utilizator ukiandreaAndreea Lucau ukiandrea Data 18 mai 2011 14:56:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <vector>
#include <list>
#include <algorithm>

struct node_t {
    std::vector<int> in_edges;
    std::vector<int> out_edges;
    bool used;
};

node_t nodes[50000];

void find_roots(int n, std::list<int> &roots)
{
    for (int i = 1; i <= n; i++)
    {
        if ((nodes[i].used == false) && (nodes[i].in_edges.size() == 0))
            roots.push_back(i);
    }
}

void sort(int n)
{
    std::vector<int> order;
    std::list<int> roots;

    find_roots(n, roots);

    while (!roots.empty()) {
        int node = roots.front();

        roots.pop_front();

        order.push_back(node);
        for (int i = 0; i < nodes[node].out_edges.size(); i++)
        {
            int m = nodes[node].out_edges.at(i);

                for (std::vector<int>::iterator it = nodes[m].in_edges.begin();
                        it != nodes[m].in_edges.end(); ++it)
                {
                    int x = *it;
                    if (x == node)
                    {
                        nodes[m].in_edges.erase(it);
                        break;
                    }
                }

            if (nodes[m].in_edges.size() == 0)
                roots.push_back(m);
        }
    }

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

int main()
{
    int m, n, i;

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

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

    for (i = 0; i < m; i++)
    {
        int x, y;

        scanf("%d %d", &x, &y);

        nodes[x].out_edges.push_back(y);
        nodes[y].in_edges.push_back(x);
    }

    sort(n);

    return 0;
}