Cod sursa(job #645120)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 8 decembrie 2011 16:43:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<set>
#include<vector>
#define minim(a,b) a<b?a:b
using namespace std;
vector<int> V[100010],Q[100010];
set<int> A;
int ST[200010],c,i,niv[100010],up[100010],m,n,top,x[200010],y[200010];
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(;m;--m)
	{
		scanf("%d%d",&x[m],&y[m]);
		V[x[m]].push_back(m);
		V[y[m]].push_back(m);
	}
}
void solve()
{
	for(i=1;i<=n;i++)if(!niv[i])DFS(i,0);
	printf("%d\n",c);
	for(i=0;i<c;i++)
	{
		A.clear();
		for(vector<int>::iterator it=Q[i].begin();it!=Q[i].end();it++)
		{
			A.insert(x[*it]);
			A.insert(y[*it]);
		//	printf("%d ",*it);
		}
		for(set<int>::iterator it=A.begin();it!=A.end();it++)
			printf("%d ",*it);
		printf("\n");
	}		

}
void DFS(int nod,int tata)
{
	int k;
	niv[nod]=up[nod]=niv[tata]+1;
	for(vector<int>::iterator it=V[nod].begin();it!=V[nod].end();it++)
	{
		int fiu=x[*it]+y[*it]-nod;
		if(fiu==tata)continue;
		if(niv[fiu]){up[nod]=minim(up[nod],up[fiu]);continue;}
		ST[++top]=*it;k=top;
		DFS(fiu,nod);
		up[nod]=minim(up[nod],up[fiu]);
		if(up[fiu]>=niv[nod])
		{
			for(;top>=k;top--)
				Q[c].push_back(ST[top]);
			c++;
		}
	}
}