Cod sursa(job #554007)

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

using namespace std;

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

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,it2;
	nivMin[nod]=nod;
	l3.push_back(nod);
	for(it=l[nod].begin();it!=l[nod].end();++it){
		if(v[*it]==0){
			df(*it);
			if(nivMin[nod]>nivMin[*it])
				nivMin[nod]=nivMin[*it];
			if(nivMin[*it]>=nod){
				it2=l3.end();
				it2--;
				while(*it2!=*it){
					l2[nr].push_back(*it2);
					l3.pop_back();
					it2=l3.end();
					it2--;
				}
				l2[nr].push_back(*it);	
				l2[nr].push_back(nod);
				l3.pop_back();
				nr++;
			}
		}
		else {
			if(nivMin[nod]>*it)
				nivMin[nod]=*it;
		}
	}
}

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");
	}
	/*for(it=l3.begin();it!=l3.end();++it){
		printf("%d ",*it);
	}*/
}

void rezolvare(){
	int i;
	for(i=1;i<=n;i++)
		if(v[i]==0){
			df(i);
			l3.pop_back();
			nr--;
		}
}

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