Pagini recente » Cod sursa (job #1379119) | Cod sursa (job #2378369) | Cod sursa (job #2259053) | Cod sursa (job #909632) | Cod sursa (job #875322)
Cod sursa(job #875322)
#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;
}