Cod sursa(job #686602)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 21 februarie 2012 19:00:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int N,M,i,j,x,y,c,lg,ST[200010],niv[100010],up[100010];
vector<int> G[100010],Q[100010];
void read(),solve(),dfs(int,int);

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void solve()
{
	for(i=1;i<=N;i++)
		if(!niv[i])
			dfs(i,0);
	printf("%d\n",c);
	for(i=1;i<=c;i++)
	{
		for(vector<int>::iterator it=Q[i].begin();it!=Q[i].end();it++)
			printf("%d ",*it);
		printf("\n");
	}
}

void dfs(int nod,int tata)
{
	int vecin;
	niv[nod]=up[nod]=niv[tata]+1;
	for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
	{
		vecin=*it;
		if(vecin==tata)continue;
		if(!niv[vecin])
		{
			ST[++lg]=nod;
			ST[++lg]=vecin;
			dfs(vecin,nod);
			up[nod]=min(up[nod],up[vecin]);
			if(up[vecin]>=niv[nod])
			{
				for(i=lg-1,j=lg;;i-=2,j-=2)
					if(ST[i]==nod&&ST[j]==vecin)
						break;
				sort(ST+i,ST+lg+1);
				c++;
				Q[c].push_back(ST[i]);
				for(j=i+1;j<=lg;j++)
					if(ST[j]!=ST[j-1])
						Q[c].push_back(ST[j]);
				lg=i-1;
			}
		}
		else
			up[nod]=min(up[nod],up[vecin]);
	}
}