Pagini recente » Cod sursa (job #220520) | Cod sursa (job #1871199) | Cod sursa (job #901376) | Cod sursa (job #1615157) | Cod sursa (job #2233202)
#include <iostream>
#include <list>
#include <stack>
#include <fstream>
using namespace std;
int V; // Number of vertices
int E; // Number of edges
// First - the vertex
// Second - the edge length
list<int> *adj; // Adjacency list
void addEdge(int v, int w) {
adj[v-1].push_back(w-1);
}
void getInput() {
ifstream f("sortaret.in");
f >> V >> E;
adj = new list<int>[V];
int v,w;
for(int i = 0; i < E; i++) {
f >> v >> w;
addEdge(v,w);
}
f.close();
}
void topological_util(int currentNode, bool *visited,stack<int> &st) {
// Mark the current node as visited
visited[currentNode] = true;
// Adjacent vertices for the current node
// c++11
// for(auto adjNode:adj[currentNode]) {}
list<int>::iterator adjNode;
for(adjNode = adj[currentNode].begin();adjNode != adj[currentNode].end();adjNode++) {
if(!visited[*adjNode]) {
topological_util(*adjNode,visited,st);
}
}
// After all its adjacent nodes are added into the stack, add the current node into the stack
st.push(currentNode);
}
void topological_sort() {
bool *visited = new bool[V];
for(int i =0 ; i < V;i++)
visited[i] = false;
stack<int> st;
for(int node = 0; node < V; node++)
if(!visited[node])
topological_util(node,visited,st);
ofstream g("sortaret.out");
// Print in topological order
while(!st.empty()) {
int node = st.top();
st.pop();
g << node + 1 << " ";
}
g.close();
delete [] visited;
}
int main () {
getInput();
topological_sort();
return 0;
}