Cod sursa(job #875293)

Utilizator whoasdas dasdas who Data 9 februarie 2013 21:25:27
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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;

    map<int, node<int>*> mp;

    for(int i = 0; i < m; i++) {
        in>>x>>y;
        if (mp.find(x) == mp.end())
            mp[x] = new node<int>(x);
        if (mp.find(y) == mp.end())
            mp[y] = new node<int>(y);
        mp[x]->neigh.push_back(mp[y]);
    }

    stack<node<int>*> res;
    for(map<int, node<int>*>::iterator it = mp.begin(); it != mp.end(); ++it) {
        if((*it).second->viz == false)
        topo_sort((*it).second, res);
    }

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