Cod sursa(job #490833)

Utilizator ConsstantinTabacu Raul Consstantin Data 8 octombrie 2010 12:00:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
#define pb push_back
using namespace std;
stack <int> s1,s2;
vector<int>v[100010],sol[ 10010 ];
int i,j,k,lvl[ 100000 ],low[ 100010 ],T[ 100010 ],l,m,n;

void citire(){
freopen("biconex.in","r",stdin);
scanf("%d %d",&n,&m);
int a,b;
for(i = 1; i <= m; i++)
	{scanf("%d %d",&a,&b);
	v[a].pb(b);
	v[b].pb(a);
	}
	
}

void PushNewSol(int a,int b){
int x,y;
k++;
do{
	x = s1.top();
	y = s2.top();
	sol[k].pb(x);
	sol[k].pb(y);
	s1.pop();
	s2.pop();
}while(!(((a==x)&&(b==y))||((a==y)&&(b==x))) );
	sort(sol[k].begin(),sol[k].end());
}

void dfs(int nod,int niv){
int N,f,i;
lvl[ nod] = low[nod] = niv;

N = v[nod].size();
for ( i = 0 ;i < N ; i++)
	{f = v[nod][i];
	if(!lvl[f])
		{s1.push(nod);
		s2.push(f);
		T[f]  = nod;
		dfs(f,niv+1);
		low[nod] = min(low[nod],low[f]);
		if(low[f] >= lvl[nod])
			PushNewSol(nod,f);
		}
	else
	if(T[nod] != f)
		low[nod] = min(low[nod],low[f]);

	}
}

void afisare(){
freopen("biconex.out","w",stdout);

int i,j;
printf("%d\n",k);
for(i = 1; i <= k ; i++)
	{for(j = 0; j < sol[i].size();j++) 
		if(sol[i][j] != sol[i][j+1])
			printf("%d ",sol[i][j]);
	printf("\n");
	}

}
int main(){
citire();
dfs(1,1);
afisare();
return 0;}