Cod sursa(job #1380241)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 7 martie 2015 00:41:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb

#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <bitset>
#include <algorithm>

const int MAX_N(100001);

int n, Bc, Level [MAX_N], LowLevel [MAX_N];
std::vector<int> Graph [MAX_N], Components [MAX_N];
std::stack<std::pair<int,int>> Stack;
std::bitset<MAX_N> Mark;

inline void Read (void)
{
	std::ifstream input("biconex.in");
	int m;
	input >> n >> m;
	int x, y;
	while (m)
	{
		input >> x >> y;
		Graph[x].push_back(y);
		Graph[y].push_back(x);
		--m;
	}
	input.close();
}

inline void Print (void)
{
	std::ofstream output("biconex.out");
	output << Bc << '\n';
	for (int i(1) ; i <= Bc ; ++i)
	{
		for (unsigned int j(0) ; j < Components[i].size() ; ++j)
			output << Components[i][j] << ' ';
		output.put('\n');
	}
	output.close();
}

void GetComponent (std::pair<int,int> e)
{
	std::vector<int> c;
	Mark.reset();
	while (Stack.top() != e)
	{
		if (!Mark[Stack.top().first])
		{
			c.push_back(Stack.top().first);
			Mark[Stack.top().first] = true;
		}
		if (!Mark[Stack.top().second])
		{
			c.push_back(Stack.top().second);
			Mark[Stack.top().second] = true;
		}
		Stack.pop();
	}
	if (!Mark[e.first])
	{
		c.push_back(e.first);
		Mark[e.first] = true;
	}
	if (!Mark[e.second])
	{
		c.push_back(e.second);
		Mark[e.second] = true;
	}
	Stack.pop();
	++Bc;
	Components[Bc] = c;
	
}

void BiconnectedComponents (int node, int parent, int depth)
{
	Level[node] = LowLevel[node] = depth;
	for (unsigned int i(0) ; i < Graph[node].size() ; ++i)
		if (Graph[node][i] == parent)
			continue;
		else if (Level[Graph[node][i]])
			LowLevel[node] = std::min(LowLevel[node],Level[Graph[node][i]]);
		else
		{
			Stack.push(std::make_pair(node,Graph[node][i]));
			BiconnectedComponents(Graph[node][i],node,depth + 1);
			LowLevel[node] = std::min(LowLevel[node],LowLevel[Graph[node][i]]);
			if (LowLevel[Graph[node][i]] >= Level[node])
				GetComponent(std::make_pair(node,Graph[node][i]));
		}
}

int main (void)
{
	Read();
	for (int i(1) ; i <= n ; ++i)
		if (!Level[i])
			BiconnectedComponents(i,i,1);
	Print();
	return 0;
}