Cod sursa(job #729802)

Utilizator ms-ninjacristescu liviu ms-ninja Data 30 martie 2012 10:15:00
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
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 x, y,i;
	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()
{
	memset(dfn,-1,sizeof(dfn));
	df(1,0,0);
	fout<<cb.size() <<'\n';
}

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