Cod sursa(job #674090)

Utilizator ukiandreaAndreea Lucau ukiandrea Data 5 februarie 2012 15:36:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.47 kb
#include <stdio.h>
#include <stdlib.h>

#include <queue>

int f_time;
int cc_index;
std::vector<std::vector<int> > components;

struct cc_node {
    cc_node(int v, int time)
    {
        value = v;
        t = time;
    }
    
    bool operator<(const cc_node &n) const
    {
        return t < n.t;
    }

    int value;
    int t;
};

std::priority_queue<cc_node> cc_nodes;

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

struct list {
	node *head;
};

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;
};

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));

	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;
}

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);
}

int dfs(graph *g, int source)
{
    f_time++;

    g->colors[source] = GRAY;

    node *n = NULL;
    if (g->adj[source]) {
        n = g->adj[source]->head;
        while (n) {
            if (g->colors[n->value] == WHITE) 
                dfs(g, n->value);
            n = n->next;
        }
    }

    f_time++;
    cc_nodes.push(cc_node(source, f_time));
}

int dfs_t(graph *g, int source)
{
    components[cc_index].push_back(source + 1);

    g->colors[source] = GRAY;

    node *n = NULL;
    if (g->adj[source]) {
        n = g->adj[source]->head;
        while (n) {
            if (g->colors[n->value] == WHITE) 
                dfs_t(g, n->value);
            n = n->next;
        }
    }
}

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

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

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

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

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

    f_time = 0;
    clear_graph_value(g);
    clear_graph_value(g_t);

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

    cc_index = 0;
    while (cc_nodes.size()) {
        cc_node n = cc_nodes.top();

        if (g_t->colors[n.value] == WHITE) {
            components.push_back(std::vector<int>());
            dfs_t(g_t, n.value);
            cc_index++;
        }

        cc_nodes.pop();
    }

    printf("%d\n", components.size());
    for (int i = 0; i < components.size(); i++) {
        for (int j = 0; j < components[i].size(); j++)
            printf("%d ", components[i][j]);
        printf("\n");
    }

	destroy_graph(&g);
	destroy_graph(&g_t);

	return 0;
}