Pagini recente » Cod sursa (job #3234028) | Cod sursa (job #729845)
Cod sursa(job #729845)
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <list>
using namespace std;
enum Color{
WHITE,
GRAY,
BLACK
};
class Node
{
public:
Color color;
int val;
vector<Node*> neigh;
Node(int v):val(v)
{
color=WHITE;
}
};
typedef vector<Node*> Graph;
int noduri;
Graph graph;
void citire()
{
map<int,Node*> gasit;
ifstream fin("sortaret.in");
int muchii;
fin>>noduri>>muchii;
for(int i=0; i<muchii; i++)
{
int start,end;
fin>>start>>end;
if(gasit.find(start)==gasit.end())
{
graph.push_back(new Node(start));
gasit[start]=graph[graph.size()-1];
}
if(gasit.find(end)==gasit.end())
{
graph.push_back(new Node(end));
gasit[end]=graph[graph.size()-1];
}
gasit[start]->neigh.push_back(gasit[end]);
}
}
list<Node *> nodes;
void dfs(Node *n)
{
if(n->color==BLACK)
return ;
n->color=GRAY;
for(int i=0; i<n->neigh.size(); i++)
dfs(n->neigh[i]);
n->color=BLACK;
nodes.push_front(n);
}
void start()
{
ofstream out("sortaret.out");
for(int i=0; i<graph.size(); i++)
if(graph[i]->color==WHITE)
dfs(graph[i]);
list<Node *>::iterator it;
for(it=nodes.begin(); it!=nodes.end(); it++)
{
out<<(*it)->val<<" ";
}
}
int main()
{
citire();
start();
return 0;
}