Cod sursa(job #1140517)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 12 martie 2014 03:02:17
Problema Componente biconexe Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
#define Nmax 100001
vector< int > v[Nmax];
vector< set<int> > l;
bool viz[Nmax];
vector< pair<int,int> > c;
int n, m, zz[Nmax], minim[Nmax], p;
int x, y;
void cmp(int x,int y)
{
	int a, b;
	set<int> s;
	vector< pair<int, int> >::iterator it;
	do{
		it=c.end();
		a=it->first; b=it->second;
		s.insert(a); s.insert(b);
		c.pop_back();
	} while(a!=x || b!=y);
	l.push_back(s);
}

void dfs(int nod,int tata,int inal)
{
	int aux;
	zz[nod]=minim[nod]=inal;
	viz[nod]=1;
	for(unsigned int i=0;i<v[nod].size();i++)
	{
		aux=v[nod][i];
		if(aux==tata) continue;
		if(!viz[aux])
		{
			c.push_back( make_pair(nod,aux) );
			dfs(aux, nod, inal+1);
			
			minim[nod]=(minim[nod] < minim[aux]) ? minim[nod] : minim[aux];
			if(minim[aux]>=zz[nod])
				cmp(nod, aux);
		} else
			minim[nod]=(minim[nod] < zz[aux]) ? minim[nod] : zz[aux];
	}
}
 
int main()
{
	freopen("biconex.in","rt",stdin);
	freopen("biconex.out","wt",stdout);
	
	scanf("%d%d",&n,&m);
	for(register int i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0,0);
	printf("%d\n",l.size());
	for(unsigned int i=0;i<l.size();i++)
	{
		for(set<int>::iterator it=l[i].begin(); it!=l[i].end(); it++)
			if(*it) printf("%d ",*it);
		printf("\n");
	}
	return 0;
}