Pagini recente » Cod sursa (job #261858) | Cod sursa (job #1389915) | Cod sursa (job #619220) | Cod sursa (job #1043286) | Cod sursa (job #442749)
Cod sursa(job #442749)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
typedef unsigned long ulong;
#define NDEBUG
#ifdef NDEBUG
#define dbg 0 && (*((ostream *) 0))
#else
#define dbg clog
#endif
class TopologicalSort
{
public:
TopologicalSort(std::vector<std::vector<ulong>* >& adjacencyList, ulong nVertices, ulong nEdges)
: numVertices(nVertices), numEdges(nEdges), adjList(adjacencyList)
{
isVisited.resize(nVertices + 1, false);
}
public:
void execute()
{
for(ulong i = 1; i < adjList.size(); i++)
{
if(!isVisited[i])
{
dfs(i);
}
}
}
void dfs(ulong node)
{
if(!isVisited[node])
{
isVisited[node] = true;
if(adjList[node])
{
for(ulong i = 0; i < adjList[node]->size(); i++)
{
dfs((*adjList[node])[i]);
}
}
solution.push_back(node);
}
}
const std::vector<ulong>& getSolution() const { return solution; }
private:
ulong numVertices;
ulong numEdges;
std::vector<std::vector<ulong>* >& adjList;
std::vector<ulong> solution;
std::vector<bool> isVisited;
};
int main(int argc, char * argv[])
{
const char * inFile = "sortaret.in";
const char * outFile = "sortaret.out";
ifstream fin(inFile);
ofstream fout(outFile);
#ifndef NDEBUG
if(!fin || !fout)
{
cerr << "Error opening one of \"" << inFile << "\" or \"" << outFile << "\"" << endl;
return -1;
}
#endif
/**
* Read the data in.
*/
ulong n, m;
fin >> n;
fin >> m;
std::vector<std::vector<ulong>* > adjList;
adjList.resize(n + 1, NULL);
ulong x, y;
for(ulong i = 0; i < m; i++)
{
fin >> x;
fin >> y;
if(adjList[x] == NULL)
{
adjList[x] = new std::vector<ulong>();
}
adjList[x]->push_back(y);
}
/**
* Solve the problem.
*/
TopologicalSort sort(adjList, n, m);
sort.execute();
const std::vector<ulong>& solution = sort.getSolution();
for(ulong i = 0; i < solution.size(); i++)
{
fout << solution[i] << " ";
}
/**
* Cleanup!
*/
for(ulong i = 0; i < adjList.size(); i++)
{
if(adjList[i] != NULL)
delete adjList[i];
}
fout.close();
fin.close();
return 0;
}