Cod sursa(job #881178)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 17 februarie 2013 19:31:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

const int MAX_SIZE(100001);

int n, m;

std::vector<int> graph [MAX_SIZE];
std::stack<std::pair<int,int> > stack;
std::vector<std::vector<int> > components;

bool mark [MAX_SIZE];
int dfn [MAX_SIZE];
int low [MAX_SIZE];

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

inline void read (void)
{
	std::freopen("biconex.in","r",stdin);
	std::scanf("%d %d",&n,&m);
	int x, y;
	for (int i(0) ; i < m ; ++i)
	{
		std::scanf("%d %d",&x,&y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	std::fclose(stdin);
}

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

void BiconnectedComponent (int x, int y)
{
	std::vector<int> nodes;
	int a, b;
	do
	{
		a = stack.top().first;
		b = stack.top().second;
		if (!mark[a])
		{
			nodes.push_back(a);
			mark[a] = true;
		}
		if (!mark[b])
		{
			nodes.push_back(b);
			mark[b] = true;
		}
		stack.pop();
	}
	while (x != a && y != b);
	for (unsigned int i(0), size(nodes.size()) ; i < size ; ++i)
		mark[nodes[i]] = false;
	components.push_back(nodes);
}

void DepthFirstSearch (int node, int number, int father)
{
	low[node] = dfn[node] = number;
	unsigned int i, size(graph[node].size());
	int neighbor;
	for (i = 0 ; i < size ; ++i)
	{
		neighbor = graph[node][i];
		if (neighbor == father)
			continue;
		if (dfn[neighbor])
			low[node] = min(low[node],dfn[neighbor]);
		else
		{
			stack.push(std::make_pair(node,neighbor));
			DepthFirstSearch(neighbor,number + 1,node);
			low[node] = min(low[node],low[neighbor]);
			if (low[neighbor] >= dfn[node])
				// node is an articulation point
				BiconnectedComponent(node,neighbor);
		}
	}
}

int main (void)
{
	read();
	for (int node(1) ; node <= n ; ++node)
		if (!dfn[node])
			DepthFirstSearch(node,1,1);
	print();
	return 0;
}