Cod sursa(job #360415)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 31 octombrie 2009 13:58:45
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <vector>

using namespace std;

vector<int> G[10000];
int Tata[10000], Lv[10000], Low[10000], Use[10000];
int Stiva[2][10000];
int i,n,m,x,y,j,Numar;
int Lungime;
vector< vector<int> > Comp;

void Nod_Critic(int nod, int fiu)
{
	int x,y;
	vector<int> c;
	Numar++;
	do{
		x = Stiva[0][Lungime];
		y = Stiva[1][Lungime--];
		c.push_back(x); c.push_back(y);
	}while (((x!=nod) || (y!=fiu)) && ((x!=fiu) || (y!=nod)));
	Comp.push_back(c);
}

void DF_Biconex(int nod)
{
	int i;
	Use[nod]=1; Low[nod]=Lv[nod];
	for (i=0; i<G[nod].size(); i++){
		if ( (G[nod][i] != Tata[nod]) && (Lv[nod] > Lv[ G[nod][i] ]) ){
			Stiva[0][++Lungime] = G[nod][i];
			Stiva[1][Lungime] = nod;
		}
		if (!Use[ G[nod][i] ]){
			Lv[ G[nod][i] ] = Lv[nod]+1;
			Tata[ G[nod][i] ] = nod;
			DF_Biconex( G[nod][i] );
			if (Low[nod] > Low[ G[nod][i] ])
				Low[nod] = Low[ G[nod][i] ];
			if (Low[ G[nod][i] ] >= Lv[nod] )
				Nod_Critic(nod, G[nod][i]);
		}
		else
			if ( (G[nod][i]!=Tata[nod]) && (Low[nod] > Lv[ G[nod][i] ]))
				Low[nod] = Lv[ G[nod][i] ];
	}
}

int main()
{
	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);
	}
	for (i=1; i<=n; i++)
		if (!Use[i]){
			Lv[i]=1;
			DF_Biconex(i);
		}
	printf("%d\n",Numar);
	for (i=0; i<Numar; i++){
		printf("%d ",Comp[i][0]);
		for (j=1; j+1<Comp[i].size(); j++)
			if (Comp[i][j]!=Comp[i][j-1])
				printf("%d ",Comp[i][j]);
		if (Comp[i][j]!=Comp[i][0])
			printf("%d\n",Comp[i][j]);
		else
			printf("\n");
	}
	return 0;
}