Cod sursa(job #430132)

Utilizator vladbBogolin Vlad vladb Data 30 martie 2010 19:35:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<fstream>
#include<vector>
#include<stack>

#define maxn 100001

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n,m,nr;
int pus[maxn],nivel[maxn],nivmin[maxn],niv[maxn],bb[maxn],t[maxn];

vector <int> v[maxn],sol[maxn];
stack < pair < int, int > > s;

void comp(int x,int y)
{	int a,b;
	nr++;
	do
	{	a=s.top().first;
		b=s.top().second;
		if(bb[a]!=nr) 
		{	sol[nr].push_back(a);
			bb[a]=nr;
		}
		if(bb[b]!=nr)
		{	sol[nr].push_back(b);
			bb[b]=nr;
		}
		s.pop();
	}while(a!=x||b!=y);
}

void df(int nod,int nivel)
{	int i,f;
	niv[nod]=nivmin[nod]=nivel;
	for(i=0;i<(int)v[nod].size();i++)
	{	f=v[nod][i];
		if(f==t[nod]) continue;
			if(!niv[f])
			{	t[f]=nod;
				s.push(make_pair(nod,f));
				df(f,nivel+1);
				
				if(nivmin[f]<nivmin[nod]) nivmin[nod]=nivmin[f];
				if(nivmin[f]>=niv[nod]) comp(nod,f);
			}
			else if(nivmin[f]<nivmin[nod]) nivmin[nod]=nivmin[f];
		
	}
}

int main()
{	int i,j,x,y;

	fin>>n>>m;
	for(i=1;i<=m;i++)
	{	fin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	df(1,1);
	
	fout<<nr<<"\n";
	
	for(i=1;i<=nr;i++)
	{	for(j=0;j<(int)sol[i].size();j++)
			fout<<sol[i][j]<<" ";
		fout<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}