Cod sursa(job #472656)

Utilizator marius.bucurBucur Marius - Ovidiu marius.bucur Data 26 iulie 2010 00:45:07
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#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]);
	}
	return 0;
	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 < (int)sorted_nodes.size(); i++)
		out << (sorted_nodes[i]->nr) << " ";
	out << "\n";
	in.close();
	out.close();
	return 0;
}