Pagini recente » Cod sursa (job #2355284) | Cod sursa (job #2098331) | Cod sursa (job #1265619) | Cod sursa (job #2222063) | Cod sursa (job #2537843)
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#define SIZE 50001
#define FIN "sortaret.in"
#define FOUT "sortaret.out"
using namespace std;
class Graph {
public:
Graph(int nNodes) {
adj = new list<int>[ nNodes + 1];
seen.resize(nNodes + 1, 0);
nodes = nNodes;
}
vector<int> topsort() {
for(int i = 1; i <= nodes; ++i) {
if(!seen[i]) {
DFS(i);
}
}
return sol;
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void DFS(int node) {
seen[node] = 1;
for(const auto&v: adj[node]) {
if(!seen[v]) {
seen[v] = 1;
DFS(v);
}
}
sol.push_back(node);
}
vector<int> getSol() {
return sol;
}
private:
list<int> *adj;
int nodes;
vector<int> seen;
vector<int> sol;
};
int main(int argc, char const *argv[])
{
int u,v, nodes, edges;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
cin>>nodes>>edges;
vector<int> sol;
Graph *g = new Graph(nodes);
while(edges--) {
cin>>u>>v;
g->addEdge(u, v);
}
sol = g->topsort();
for(vector<int>::reverse_iterator it = sol.rbegin(); it != sol.rend(); ++it)
cout<<*it<<" ";
return 0;
}