Cod sursa(job #728803)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 28 martie 2012 23:20:29
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<cstdio>
#include<bitset>
#include<vector>
#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;

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)
{
	vector<int> inter;
	while(st[0]>0)
	{
		inter.push_back(st[st[0]]);
		st[0]--;
	}
	inter.push_back(i);
	rez.push_back(inter);
}

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])
		{
			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);
		}
		else if(fiu!=t[i]&&l[i]>nv[fiu])
			l[i]=nv[fiu];
	}
	
	st[++st[0]]=i;
}

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;
}