Pagini recente » Cod sursa (job #2756193) | Cod sursa (job #1038439) | Cod sursa (job #2523597) | Cod sursa (job #2450788) | Cod sursa (job #996349)
Cod sursa(job #996349)
#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;
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);
}