Cod sursa(job #672406)

Utilizator ukiandreaAndreea Lucau ukiandrea Data 2 februarie 2012 00:55:04
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.3 kb
#include <stdio.h>
#include <stdlib.h>

#include <queue>

struct node {
	int value;
	int weight;
	struct node *next;
};

struct list {
	node *head;
};

int dfs_time;
std::vector<int> order;

list* create_list()
{
	list *l = (list*)calloc(1, sizeof(list));
	l->head = NULL;
	return l;
}

void insert_list(list* l, int value, int weight)
{
	if (l->head == NULL) {
		l->head = (node*)calloc(1, sizeof(node));
		l->head->value = value;
		return;
	}

	node *p = l->head;
	while (p->next != NULL)
		p = p->next;

	node *n = (node*)calloc(1, sizeof(node));
	n->value = value;
	n->weight = weight;
	p->next = n;
}

void destroy_list(list **l)
{
	while ((*l)->head != NULL) {
		node *p = (*l)->head;
		(*l)->head = (*l)->head->next;
		
		free(p);
	}
}

enum colors {
	WHITE = 0,
	GRAY,
	BLACK
};

struct graph {
	int n;
	list **adj;
	int *colors;
	int *parents;
};

graph* create_graph(int size)
{
	graph *g = (graph*)calloc(1, sizeof(graph));
	g->n = size;
	g->adj = (list**)calloc(size, sizeof(list*));
	g->colors = (int*)calloc(size, sizeof(int));
	g->parents = (int*)calloc(size, sizeof(int));

	return g;
}

void add_graph_edge(graph *g, int v1, int v2, int w)
{
	if (g->adj[v1] == NULL) 
		g->adj[v1] = create_list();

	insert_list(g->adj[v1], v2, w);
}

void clear_graph_value(graph *g)
{
	for (int i = 0; i < g->n; i++) {
		g->colors[i] = WHITE;
		g->parents[i] =  -1;
	}
}

void destroy_graph(graph **g)
{
	for (int i = 0; i < (*g)->n; i++) {
		if ((*g)->adj[i])
			destroy_list(&((*g)->adj[i]));
	}

	free((*g)->adj);
	free((*g)->colors);
	free((*g)->parents);
	free(*g);
}

void bfs(graph *g, int s)
{
	std::queue<int> nodes;

	clear_graph_value(g);

	g->colors[s] = GRAY;
	g->parents[s] = -1;

	nodes.push(s);
	while (nodes.size()) {
		int x = nodes.front();
		printf("%d ", x);
		node *n = NULL;
		if (g->adj[x])
			n = g->adj[x]->head;

		while (n) {
			if (g->colors[n->value] == WHITE) {
				g->colors[n->value] = GRAY;
				g->parents[n->value] = x;
				nodes.push(n->value);
			}
			n = n->next;
		}
		nodes.pop();
		g->colors[x] = BLACK;
	}

	printf("\n");
}

void print_graph_path(graph *g, int source, int dest)
{
	int x = dest;
	std::vector<int> path;

	do {
		path.push_back(x);
		x = g->parents[x];
	} while (x != -1);

	printf("Path from %d to %d\n", source, dest);
	for (std::vector<int>::reverse_iterator it = path.rbegin(); 
			it != path.rend(); ++it) {
		printf("%d ", *it);
	}
	printf("\n");
}

void dfs(graph *g, int x)
{	
	//g->start_time[node] = dfs_time;
	//dfs_time++;
	
	node *n = NULL;
	if (g->adj[x])
		n = g->adj[x]->head;

	while (n) {
		if (g->colors[n->value] == WHITE) {
			g->colors[n->value] = GRAY;
			g->parents[n->value] = x;
			dfs(g, n->value);
		}
		n = n->next;
	}

	//g->end_time[node] = dfs_time;
	dfs_time++;
	order.push_back(x);
}

int main()
{
	int v, e;
	graph * g = NULL;

	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	scanf("%d %d\n", &v, &e);
	g = create_graph(v);

	for (int i = 0; i < e; i++) {
		int v1, v2, w;

		scanf("%d %d\n", &v1, &v2);
		add_graph_edge(g, v1 - 1, v2 - 1, 0);
	}

	int dfs_time = 0;
	clear_graph_value(g);

	for (int i = 0; i < g->n; i++) {
		if (g->colors[i] == WHITE)
			dfs(g, i);
	}

	for (std::vector<int>::reverse_iterator it = order.rbegin(); it != order.rend(); ++it)
		printf("%d ", *it + 1);
	printf("\n");

	destroy_graph(&g);

	return 0;
}