Pagini recente » Cod sursa (job #2389674) | Cod sursa (job #2702744) | Cod sursa (job #2481841) | Cod sursa (job #2516033) | Cod sursa (job #472655)
Cod sursa(job #472655)
#include<queue>
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<map>
#define MAX_NODES 50000
#define MAX_VERTICES 100000
using namespace std;
struct Vertice;
struct Node{
int in;
int out;
struct Vertice** vertices;
int vertices_nr;
int vertices_capacity;
int nr;
};
typedef struct Node node_t;
struct Vertice
{
node_t* node_from;
node_t* node_to;
};
typedef struct Vertice vertice_t;
node_t* new_node(int n)
{
node_t* nod = (node_t*)malloc(sizeof(node_t));
nod->nr = n;
nod->vertices_nr = 0;
nod->in = 0;
nod->out = 0;
nod->vertices_capacity = 2;
nod->vertices = (vertice_t**)calloc(2, sizeof(vertice_t*));
return nod;
}
vertice_t* add_vertice(node_t* from, node_t* to)
{
vertice_t* v = (vertice_t*)malloc(sizeof(vertice_t));
v->node_from = from;
v->node_to = to;
from->out++;
to->in++;
if(from->vertices_capacity == from->vertices_nr)
{
from->vertices = (vertice_t**)realloc(from->vertices, from->vertices_capacity*2);
from->vertices_capacity *= 2;
}
from->vertices[from->vertices_nr++] = v;
return v;
}
node_t* nodes[MAX_NODES];
std::vector<node_t*> sorted_nodes;
int main()
{
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int M,N;
in >> N >> M;
int i = 0;
for(i = 1; i <= N; i++)
nodes[i] = new_node(i);
i = 0;
int from, to;
for(i = 1; i <= M; i++)
{
in >> from >> to;
add_vertice(nodes[from], nodes[to]);
}
std::queue<node_t*> Q;
for(i = 1; i <= N; i++)
if(nodes[i]->in == 0)
Q.push(nodes[i]);
while(Q.size())
{
node_t* n = Q.front();
Q.pop();
sorted_nodes.push_back(n);
for(i = 0; i < n->vertices_nr; i++)
{
vertice_t* node_vertice = n->vertices[i];
node_vertice->node_to->in--;
if(node_vertice->node_to->in == 0)
Q.push(node_vertice->node_to);
}
}
for(i = 0; i < sorted_nodes.size(); i++)
out << (sorted_nodes[i]->nr) << " ";
out << "\n";
in.close();
out.close();
}