Cod sursa(job #856454)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 16 ianuarie 2013 15:26:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb

#include <cstdio>

const int MAX_N(100001);

int n, m;

struct list
{
	int node;
	struct list *next;
} *graph [MAX_N];

int stack [MAX_N], top;
int components;
int component [MAX_N], index;
int component_size [MAX_N];
int identifier;
int link [MAX_N];
int lower_link [MAX_N];
bool in_stack [MAX_N];

inline void add (int x, int y)
{
	struct list *new_edge(new struct list);
	new_edge->node = y;
	new_edge->next = graph[x];
	graph[x] = new_edge;
}

inline void read (void)
{
	std::freopen("ctc.in","r",stdin);
	std::scanf("%d %d",&n,&m);
	int x, y;
	for (int counter(0) ; counter < m ; ++counter)
	{
		std::scanf("%d %d",&x,&y);
		add(x,y);
	}
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("ctc.out","w",stdout);
	std::printf("%d\n",components);
	int i, j(0), end(0);
	for (i = 0 ; i < components ; ++i)
	{
		end += component_size[i];
		while (j < end)
		{
			std::printf("%d ",component[j]);
			++j;
		}
		std::putchar('\n');
	}
	std::fclose(stdout);
}

inline int min (int a, int b)
{
	return a < b ? a : b;
}

inline void StronglyConnectedComponents (int root)
{
	int size(0);
	while (stack[top] != root)
	{
		component[index] = stack[top];
		in_stack[component[index]] = false;
		++index;
		++size;
		--top;
	}
	--top;
	component[index] = root;
	++index;
	component_size[components] = size + 1;
	++components;
}

void DepthFirstSearch (int vertex)
{
	++identifier;
	link[vertex] = lower_link[vertex] = identifier;
	++top;
	stack[top] = vertex;
	in_stack[vertex] = true;
	for (struct list *iterator(graph[vertex]) ; iterator ; iterator = iterator->next)
	{
		if (link[iterator->node])
		{
			if (in_stack[iterator->node])
				lower_link[vertex] = min(lower_link[vertex],lower_link[iterator->node]);
		}
		else
		{
			DepthFirstSearch(iterator->node);
			lower_link[vertex] = min(lower_link[vertex],lower_link[iterator->node]);
		}
	}
	if (link[vertex] == lower_link[vertex])
		StronglyConnectedComponents(vertex);
}

inline void Tarjan (void)
{
	for (int vertex(1) ; vertex <= n ; ++vertex)
		if (!link[vertex])
			DepthFirstSearch(vertex);
}

int main (void)
{
	read();
	Tarjan();
	print();
	return 0;
}