Cod sursa(job #728835)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 29 martie 2012 00:13:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include<cstdio>
#include<bitset>
#include<deque>
#include<vector>
#include<algorithm>
#define dim 8192

using namespace std;

int i,j,n,m,nv[100024],t[100024],l[100024],st[100024],pz;
char c[dim+3];

vector<int> a[100024];
bitset<100024> fol;
deque< pair<int,int> > q;
vector< vector<int> > rez;

inline void cit(int &x)
{
	x=0;
	
	while(c[pz]<'0'||c[pz]>'9')
		if(++pz==dim) fread(c,dim,1,stdin),pz=0;
	
	while(c[pz]>='0'&&c[pz]<='9')
	{
		x=x*10+c[pz]-'0';
		if(++pz==dim) fread(c,dim,1,stdin),pz=0;
	}
}

void scoate(int i,int fiu)
{
	int a,b;
	vector<int> inter,inter1;
	do
	{
		a=q.back().first;
		b=q.back().second;
		inter.push_back( q.back().first);
		inter.push_back( q.back().second);
		q.pop_back();
		
	}while(a!=i&&b!=fiu);
	
	sort(inter.begin(),inter.end());
	
	inter1.push_back(inter[0]);
	for(i=1;i<inter.size();++i) if(inter[i]!=inter[i-1]) inter1.push_back(inter[i]);
	
	rez.push_back(inter1);
}

void dfs(int i)
{
	fol[i]=1;
	l[i]=nv[i];
	
	for(int j=0;j<a[i].size();++j)
	{
		int fiu=a[i][j];
		
		if(!fol[fiu])
		{
			q.push_back( make_pair(i,fiu));
			t[fiu]=i;
			nv[fiu]=nv[i]+1;
			
			dfs(fiu);
			
			if(l[i]>l[fiu]) l[i]=l[fiu];
			if(l[fiu]>=nv[i]) scoate(i,fiu);
		}
		else if(fiu!=t[i]&&l[i]>nv[fiu])
			l[i]=nv[fiu];
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	
	cit(n);
	cit(m);
	
	for(i=1;i<=m;++i)
	{
		int x=0,y=0;
		cit(x);
		cit(y);
		
		a[x].push_back(y);
		a[y].push_back(x);
	}
	
	for(i=1;i<=n;++i)
		if(!fol[i])
		{
			nv[i]=1;
			dfs(i);
		}
		
	printf("%d\n",rez.size());
	
	for(i=0;i<rez.size();++i)
	{
		for(j=0;j<rez[i].size();++j) printf("%d ",rez[i][j]);
		printf("\n");
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}