Cod sursa(job #610573)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 28 august 2011 04:54:04
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>

#define MAXN 	100005

#define minimum(a,b)	\
({\
	typeof(a) _a = a;	\
	typeof(b) _b = b;	\
	_a<=_b?_a:_b;		\
})

using namespace std;

typedef vector<vector<int> > Graph;
Graph graph;

int low[MAXN];
int discTime[MAXN];
stack<pair<int, int> > stEdges;
vector<vector<int> > BiComps;

void AddBiComp(const int x, const int y)
{
	vector<int> comp;

	while(!stEdges.empty())
	{
		const pair<int, int> edge = stEdges.top();
		stEdges.pop();
		
		comp.push_back(edge.first);
		comp.push_back(edge.second);
		
		if (edge.first == x && edge.second == y)
			break;
	}
	
	if (comp.size())
		BiComps.push_back(comp);
}

void AddLeftOver()
{
	vector<int> comp;

	while(!stEdges.empty())
	{
		const pair<int, int> edge = stEdges.top();
		stEdges.pop();
		
		comp.push_back(edge.first);
		comp.push_back(edge.second);
	}
	
	if (comp.size())
		BiComps.push_back(comp);
}

void DFS
(
	const int node,
	const int parent,
	const int depth
)
{
	vector<int>::iterator it;
	discTime[node] = low[node] = depth;
	
	for (it=graph[node].begin(); it!=graph[node].end(); ++it)
	{
		if (*it != parent)
		{
			if (discTime[*it] == -1)
			{
				stEdges.push(make_pair(node, *it));
				DFS(*it, node, depth+1);
				
				low[node] = minimum(low[node], low[*it]);
				
				if (low[*it] >= discTime[node])
				{
					AddBiComp(node, *it);
				}
			}
			else
			{
				low[node] = minimum(low[node], discTime[*it]);
			}
		}
	}
}

int main()
{
	int n,m;
	fstream fin("biconex.in", fstream::in);
	fstream fout("biconex.out", fstream::out);
	
	fin >> n >> m;
	//cout << n << " " << m << endl;
	
	graph.resize(n);
	
	for (int i=0; i<m; ++i)
	{
		int x, y;
		fin >> x >> y;
		
		graph[x-1].push_back(y-1);
		graph[y-1].push_back(x-1);
		
		discTime[i] = -1;
	}
	
	//memset(discTime, 0xFFFFFFFF, (n+1)*sizeof(int));
	DFS(0,-1,0);
	AddLeftOver();
	
	fout << BiComps.size() << "\n";
	for (int i=0; i<BiComps.size(); ++i)
	{
		sort(BiComps[i].begin(), BiComps[i].end());
		BiComps[i].erase(unique(BiComps[i].begin(), BiComps[i].end()), BiComps[i].end());
		for (int j=0; j<BiComps[i].size(); ++j)
		{
			fout << BiComps[i][j]+1 << " ";
		}
		fout << "\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}