Pagini recente » Cod sursa (job #1630820) | Cod sursa (job #1429927) | Cod sursa (job #1001001) | Cod sursa (job #1463871) | Cod sursa (job #1457679)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
///// DESCRIPTION
// THIS PROGRAM PERFORMS A TOPOLOGICAL SORT
// OF THE VERTICES OF A DIRECTED ACYCLIC GRAPH
// BY DEPTH-FIRST SEARCH (DFS)
/////
void visit(int, vector<int>&, vector<int>&, vector<int>[]);
int main(int argc, char **argv)
{
// INPUT
ifstream indata("sortaret.in");
int n, m;
indata >> n >> m;
vector<int> edges[n];
vector<int> unvisited;
// input data
int x, y;
for (int i = 0; i < m; i++) {
indata >> x >> y;
// set edges
edges[x - 1].push_back(y - 1);
}
for (int i = 0; i < n; i++) {
// set unvisited nodes,
// i.e. all right now
unvisited.push_back(0);
}
indata.close();
// TOPOLOGICAL SORT
vector<int> topologicalSort;
for (int i = 0; i < n; i++) {
visit(i, topologicalSort, unvisited, edges);
}
// OUTPUT
ofstream outdata("sortaret.out");
for (int i = n-1; i >= 0; i--) {
outdata << (topologicalSort[i] + 1) << " ";
}
outdata.close();
return 0;
}
void visit(int node, vector<int>& topologicalSort, vector<int>& unvisited, vector<int> edges[]) {
if (unvisited[node] == 0) {
unvisited[node] = 1;
for(vector<int>::iterator vit = edges[node].begin(); vit < edges[node].end(); vit++) {
visit(*vit, topologicalSort, unvisited, edges);
}
topologicalSort.push_back(node);
}
}