Cod sursa(job #530295)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 7 februarie 2011 14:20:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
const int M=200005;
vector<int> L[N],SOL[N];
bool f[N];
int q,nrs,n,m,niv[N],low[N],tata[N],st[M][2];
void read()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		L[x].push_back(y);
		L[y].push_back(x);
	}
}
void df(int nod)
{
	f[nod]=1;
	low[nod]=niv[nod];
	for(vector<int>::iterator it=L[nod].begin();it!=L[nod].end();it++)
	{
		int fiu=*it;
		if(!f[fiu])
		{
			tata[fiu]=nod;
			niv[fiu]=niv[nod]+1;
			++q;
			st[q][0]=nod;
			st[q][1]=fiu;
			df(fiu);
			if(low[fiu]<low[nod])
				low[nod]=low[fiu];
			if(low[fiu]>=niv[nod])
			{
				++nrs;
				while(!(st[q][0]==nod && st[q][1]==fiu))
				{
					SOL[nrs].push_back(st[q][0]);
					SOL[nrs].push_back(st[q][1]);
					--q;
				}
				SOL[nrs].push_back(st[q][0]);
				SOL[nrs].push_back(st[q][1]);
				--q;
			}
		}
		else
		{
			if(tata[nod]!=fiu && niv[fiu]<niv[nod])
			{
				if(low[nod]>niv[fiu]) low[nod]=niv[fiu];
				++q;
				st[q][0]=nod;
				st[q][1]=fiu;
			}
		}
	}
}
void afis()
{
	printf("%d\n",nrs);
	for(int i=1;i<=nrs;i++)
	{
		int last=-1;
		sort(SOL[i].begin(),SOL[i].end());
		for(vector<int>::iterator it=SOL[i].begin();it!=SOL[i].end();it++)
		{
			if(*it!=last)
				printf("%d ",*it);
			last=*it;
		}
		printf("\n");
	}
}
int main()
{
	read();
	df(1);
	afis();
	return 0;
}