Pagini recente » Cod sursa (job #342053) | Cod sursa (job #958100) | Cod sursa (job #1026330) | Cod sursa (job #2224724) | Cod sursa (job #1705513)
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <list>
typedef std::list<int> List;
class Graph
{
int nodes;
List *adjList, *topsort_res;
void visit(int root, bool *visited);
public:
Graph(int nodes);
~Graph();
void insert(int u, int v);
List *topsort();
};
Graph::Graph(int nodes) {
this->nodes = nodes;
adjList = new List[nodes];
topsort_res = NULL;
}
Graph::~Graph() {
if (topsort_res) delete topsort_res;
}
inline void Graph::insert(int u, int v) {
adjList[u].push_back(v);
}
void Graph::visit(int root, bool *visited) {
visited[root] = true;
for (List::iterator neigh = adjList[root].begin();
neigh != adjList[root].end(); neigh++)
if (!visited[*neigh]) visit(*neigh, visited);
topsort_res->push_front(root);
}
List *Graph::topsort() {
bool *visited = new bool[nodes];
std::memset(visited, false, nodes);
topsort_res = new List();
// Sortare topologica
for (int node = 0; node < nodes; node++)
if (!visited[node])
visit(node, visited);
delete[] visited;
return topsort_res;
}
int main(int argc, char **argv) {
std::ifstream input("sortaret.in");
std::ofstream output("sortaret.out");
Graph *graph;
int N, M, u, v;
if (!input.is_open() || !output.is_open()) {
std::cerr << "Cannot open input/output file!" << std::endl;
return -1;
}
input >> N >> M;
graph = new Graph(N);
while(input >> u >> v)
graph->insert(u - 1, v - 1);
List *result = graph->topsort();
for (List::iterator it = result->begin(); it != result->end(); it++)
output << (*it + 1) << " ";
delete graph;
return 0;
}