Cod sursa(job #335433)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 29 iulie 2009 22:37:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;

vector <int> v[100000];
vector <int> componente[100000];
stack < pair <int,int> > s;
int nc=0,viz[100000],df[100000],timp=0,jos[100000];

int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}

void scoate(int x,int y)
{
	int xx,yy;

	do
	{
		xx=s.top().first;
		yy=s.top().second;
		s.pop();
		componente[nc].push_back(xx);
		componente[nc].push_back(yy);
	}
	while(xx!=x || yy!=y);
	nc++;
}

void biconex(int rad,int tata)
{
	int i,nod;

	jos[rad]=timp;
	df[rad]=timp;
	timp++;
	for(i=0;i<(int) v[rad].size();i++)
	{
		nod=v[rad][i];
		if(nod!=tata && df[nod]<df[rad])
			s.push(make_pair(rad,nod));
		if(df[nod]==-1)
		{
			biconex(nod,rad);
			jos[rad]=min(jos[rad],jos[nod]);
			if(jos[nod]>=df[rad])
				scoate(rad,nod);
		}
		else if(nod!=tata)
			jos[rad]=min(jos[rad],df[nod]);
	}
}
			
int main()
{
	int n,m,a,b,i,j;
	FILE *f=fopen("biconex.in","r");

	fscanf(f,"%i%i\n",&n,&m);
	for(i=0;i<m;i++)
	{
		fscanf(f,"%i%i\n",&a,&b);
		v[a-1].push_back(b-1);
		v[b-1].push_back(a-1);
	}
	fclose(f);

	f=fopen("biconex.out","w");
	for(i=0;i<n;i++)
		df[i]=-1;
	biconex(0,-1);

	fprintf(f,"%i\n",nc);
	for(i=0;i<nc;i++)
	{
		for(j=0;j<(int) componente[i].size();j++)
			viz[componente[i][j]]=0;
		for(j=0;j<(int) componente[i].size();j++)
		{
			if(viz[componente[i][j]]==0)
			{
				viz[componente[i][j]]=1;
				fprintf(f,"%i ",componente[i][j]+1);
			}
		}
		fprintf(f,"%s","\n");
	}			
	fclose(f);
	return 0;
}