Cod sursa(job #553906)

Utilizator paul24090FMI - Balauru Paul paul24090 Data 14 martie 2011 13:37:01
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <list>

using namespace std;

int n,m,v[100003],nr1=0,nivMin[100003],punctDeInflexiune[100003],nr=1,t[100003];
list<int> l[100003];
list<int> l2[100003];

void citire(){
	scanf("%d %d",&n,&m);
	int i,x,y;
	for(i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		l[x].push_back(y);
		l[y].push_back(x);
	}
}

void df(int nod){
	v[nod]=1;
	list<int>::iterator it;
	nivMin[nod]=nod;
	for(it=l[nod].begin();it!=l[nod].end();++it){
		if(v[*it]==0){
			df(*it);
			t[*it]=nod;
			if(nod!=1){
				if(nivMin[nod]>nivMin[*it])
					nivMin[nod]=nivMin[*it];
				if(nivMin[*it]>=nod && punctDeInflexiune[nod]==0){
					punctDeInflexiune[nod]=1;
				}
			}
		}
		else {
			if(nivMin[nod]>*it)
				nivMin[nod]=*it;
		}
	}
}

void df2(int nod){
	v[nod]=1;
	list<int>::iterator it;
	for(it=l[nod].begin();it!=l[nod].end();++it)
		if(v[*it]==0){
			df2(*it);
		}
	if(!(punctDeInflexiune[1]==1 && nod==1))
		l2[nr].push_back(nod);
	if(punctDeInflexiune[t[nod]]==1){
		l2[nr].push_back(t[nod]);
		nr++;
	}
}



void initV(){
	int i;
	for(i=1;i<=n;i++)
		v[i]=0;
}

void afisare(){
	int i;
	printf("%d\n",nr);
	list<int>::iterator it;
	for(i=1;i<=nr;i++){
		for(it=l2[i].begin();it!=l2[i].end();++it){
			printf("%d ",*it);
		}
		printf("\n");
	}
}

void rezolvare(){
	df(1);
	list<int>::iterator it;
	for(it=l[1].begin();it!=l[1].end();++it)
		nr1++;
	if(nr1>1){
		punctDeInflexiune[1]=1;
	}
	initV();
	df2(1);
	if(punctDeInflexiune[1]==1)
		nr--;
}

int main(){
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	citire();
	rezolvare();
	afisare();
	return 0;
}