Pagini recente » Cod sursa (job #3158649) | Cod sursa (job #2877565) | Cod sursa (job #1994035) | Cod sursa (job #2251770) | Cod sursa (job #996351)
Cod sursa(job #996351)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <cstdlib>
enum Color
{
WHITE, GREY, BLACK
};
struct Vertex
{
int u;
std::vector<int> myV;
Vertex() : u(), myV() {}
};
void visit(Vertex *A, Color *B, int u, std::deque<int> &myS);
void toposort(Vertex *A, int nV, std::deque<int> &myS);
int main()
{
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
int nV, nE, a, b;
in >> nV >> nE;
Vertex *Arr = new Vertex[nV + 1];
for(int i = 1; i <= nV; i++)
Arr[i].u = i;
for(int i = 0; i < nE; i++)
in >> a >> b, Arr[a].myV.push_back(b);
std::deque<int> myS;
toposort(Arr, nV, myS);
while(!myS.empty())
out << myS.front() << ' ', myS.pop_front();
return 0;
}
void visit(Vertex *A, Color *B, int u, std::deque<int> &myS)
{
if(B[u] == GREY)
{
exit(1);
}
if(B[u] == BLACK) return;
B[u] = GREY;
for(unsigned i = 0; i < A[u].myV.size(); i++)
visit(A, B, A[u].myV[i], myS);
B[u] = BLACK;
myS.push_front(u);
}
void toposort(Vertex *A, int nV, std::deque<int> &myS)
{
Color *B = new Color[nV + 1];
for(int i = 0; i <= nV; i++)
B[i] = WHITE;
for(int i = 1; i <= nV; i++)
if(B[i] == WHITE) visit(A, B, i, myS);
}