Cod sursa(job #432368)

Utilizator GotenAmza Catalin Goten Data 2 aprilie 2010 12:05:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#define nmax 100100
using namespace std;
vector <int> v[nmax],sol[2*nmax];
vector <pair <int, int> > s;
int acc[nmax],niv[nmax],u[nmax];
int nr;
void dfs(int nod, int pre)
{
	acc[nod]=niv[nod]=niv[pre]+1;
	u[nod]=1;
	vector<int> :: iterator fiu;
	for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
		if(*fiu!=pre)
			if(!u[*fiu])
			{
				s.push_back(make_pair(nod,*fiu));
				dfs(*fiu,nod);
				if(acc[nod]>acc[*fiu])
					acc[nod]=acc[*fiu];
				if(acc[*fiu]>=niv[nod])
				{
					nr++;
					while(s.back().first!=nod)
					{
						sol[nr].push_back(s.back().second);
						s.pop_back();
					}
					sol[nr].push_back(nod);
					sol[nr].push_back(s.back().second);
					s.pop_back();
				}
			}
			else
				if(acc[nod]>niv[*fiu])
					acc[nod]=niv[*fiu];
}		
int main()
{
	int m,x,y,i,n;
	ifstream read("biconex.in");
	ofstream write("biconex.out");
	read>>n>>m;
	while(m--)
	{
		read>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	write<<nr<<'\n';
	vector<int> :: iterator fiu;
	for(i=1;i<=nr;i++)
	{
		for(fiu=sol[i].begin();fiu!=sol[i].end();fiu++)
			write<<*fiu<<' ';
		write<<'\n';
	}
	return 0;
}