Pagini recente » Cod sursa (job #330301) | Cod sursa (job #1669312) | Cod sursa (job #77899) | Cod sursa (job #872888) | Cod sursa (job #875293)
Cod sursa(job #875293)
#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;
}