Cod sursa(job #875322)

Utilizator whoasdas dasdas who Data 9 februarie 2013 21:58:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <list>
#include <map>
#include <stack>

using namespace std;

template<class T>
class node {
    public:
    T label;
    bool viz;
    list<node*> neigh;
    node(T x)
    {
        label = x;
        viz = false;
    }
};

void topo_sort(node<int>* root, stack<node<int>*> &res)
{
    if(root) {
        root->viz = true;
        for(list<node<int>*>::iterator it = root->neigh.begin(); it != root->neigh.end(); ++it)
            if((*it)->viz == false)
                topo_sort(*it, res);
        res.push(root);
    }
}


int main()
{
    int n, m, x, y;
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    in>>n>>m;

    node<int>** nd = new node<int>*[n+1];
    for (int i = 1; i <=n; i++)
        nd[i] = new node<int>(i);

    for(int i = 0; i < m; i++) {
        in>>x>>y;
        nd[x]->neigh.push_back(nd[y]);
    }

    stack<node<int>*> res;
    for(int i = 1; i <= n; i++) {
        if(nd[i]->viz == false)
            topo_sort(nd[i], res);
    }
    if(res.size() != n)
        out<<"problemo! res.size = "<<res.size()<<endl;

    while(!res.empty()) {
        out<<res.top()->label<<" ";
        res.pop();
    }
    return 0;
}