Cod sursa(job #727553)

Utilizator ms-ninjacristescu liviu ms-ninja Data 28 martie 2012 08:33:50
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
#define dim 100005
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> v[dim];
stack < pair <int,int> > stiva;
vector <vector <int> > cb;
int dfn[dim],n,m,lv[dim];

void read()
{
	int i, x, y;
	fin>>n >>m;
	
	for(i=1;i<=m;++i)
	{
		fin>>x >>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

void baga (int nod1, int nod2)
{
	vector <int> cbnr;
	int x, y;
	
	do
	{
		x=stiva.top().first;
		y=stiva.top().second;
		stiva.pop();
		cbnr.push_back(x);
		cbnr.push_back(y);
		
	}while(x!=nod1 || y!=nod2);
	
	cb.push_back(cbnr);
}

void df(int nod, int tata, int level)
{
	dfn[nod]=level;
	lv[nod]=level;
	for(int k=0;k<(int)v[nod].size();++k)
		if(v[nod][k]!=tata)
			if(dfn[v[nod][k]]==-1)
			{
				stiva.push(make_pair(nod,v[nod][k]));
				df(v[nod][k],nod,level+1);
				lv[nod]=min(lv[nod],lv[v[nod][k]]);
				if(lv[v[nod][k]]>=dfn[nod])
					baga(nod,v[nod][k]);
			}
			else
				lv[nod]=min(lv[nod],lv[v[nod][k]]);
}

void solve()
{
	vector <int> ::iterator it;
	memset(dfn,-1,sizeof(dfn));
	df(1,0,0);
	fout<<cb.size()<<'\n';
	
	for(int i=0;i<(int)cb.size();++i)
	{
		sort(cb[i].begin(),cb[i].end());
		cb[i].erase(unique(cb[i].begin(),cb[i].end()),cb[i].end() );
		for(it=cb[i].begin();it!=cb[i].end();++it)
			fout<<*it <<" ";
		fout<<'\n';
	}
}

int main()
{
	read();
	solve();
	return 0;
}