Cod sursa(job #859071)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 19 ianuarie 2013 17:39:14
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb

#include <cstdio>

const int MAX_N(100001);

int n, m, components;
int component_size [MAX_N];
int component [MAX_N], add_node;
int link [MAX_N], low_link [MAX_N];
bool out_stack [MAX_N];

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

struct edge
{
	int x;
	int y;
} stack [MAX_N];

inline bool operator != (struct edge a, struct edge b)
{
	return (a.x != b.x && a.y != b.y);
}

inline struct edge make_edge (int x, int y)
{
	struct edge result;
	result.x = x;
	result.y = y;
	return result;
}

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

int top;

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("biconex.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);
		add(y,x);
	}
	std::fclose(stdin);
}

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

inline void push (const struct edge &e)
{
	stack[top] = e;
	++top;
}

void BiconnectedComponent (const struct edge &e)
{
	int size(0);
	do
	{
		--top;
		if (!out_stack[stack[top].x])
		{
			component[add_node] = stack[top].x;
			++add_node;
			++size;
			out_stack[stack[top].x] = true;
		}
		if (!out_stack[stack[top].y])
		{
			component[add_node] = stack[top].y;
			++add_node;
			++size;
			out_stack[stack[top].y] = true;
		}
	}
	while (stack[top] != e);
	component_size[components] = size;
	++components;
	for (int index(add_node - size) ; index < add_node ; ++index)
		out_stack[component[index]] = false;
}

void DepthFirstSearch (const int node, const int father, const int depth)
{
	struct edge e;
	link[node] = low_link[node] = depth;
	for (struct list *iterator(graph[node]) ; iterator ; iterator = iterator->next)
	{
		if (iterator->node == father)
			continue;
		if (link[iterator->node])
			low_link[node] = min(low_link[node],link[iterator->node]);
		else
		{
			e.x = node;
			e.y = iterator->node;
			push(e);
			DepthFirstSearch(iterator->node,node,depth + 1);
			low_link[node] = min(low_link[node],low_link[iterator->node]);
			if (low_link[iterator->node] >= link[node])
				BiconnectedComponent(make_edge(node,iterator->node));
		}
	}
}

int main (void)
{
	read();
	DepthFirstSearch(1,0,1);
	print();
	return 0;
}