Cod sursa(job #398337)

Utilizator otilia_sOtilia Stretcu otilia_s Data 18 februarie 2010 15:16:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX=100004;
const int MMAX=200004;
vector <int> A[NMAX],CB[NMAX];
int dfn[NMAX],low[NMAX], S[MMAX][2],nv[NMAX];
int ns,n,ncb;
bool viz[NMAX];

void citire()
{
	FILE *fin=fopen("biconex.in","r");
	int m;
	fscanf(fin,"%d%d",&n,&m);
	int x,y;
	while (m--)
	{
		fscanf(fin,"%d%d",&x,&y);
		A[x].push_back(y);
		A[y].push_back(x);
	}
	for (int i=1;i<=n;++i) nv[i]=A[i].size();
	fclose(fin);
}

void comp_bicon(int tx, int x)
{
	ncb++;	
	do
	{
		CB[ncb].push_back(S[ns][1]);
	}
	while (S[ns--][0]!=tx);	
	CB[ncb].push_back(S[ns+1][0]);
}

void biconex(int tx, int x)
{ int i,y;
	dfn[x]=low[x]=dfn[tx]+1; viz[x]=1;
	for (i=0;i<nv[x];++i)
	{
		y=A[x][i];
		if (y==tx) continue;
		if (viz[y]) { low[x]=min(low[x],dfn[y]);}
		   else
		   {
			S[++ns][0]=x; S[ns][1]=y;
			biconex(x,y);
			low[x]=min(low[x],low[y]);
			if (low[y]>=dfn[x]) comp_bicon(x,y);
		   }	
	}
}

void afisare()
{
	FILE *fout=fopen("biconex.out","w");
	fprintf(fout,"%d\n",ncb);
	int i,j;
	for (i=1;i<=ncb;++i)
	{			
		for (j=CB[i].size()-1; j>=0;--j)
			fprintf(fout,"%d ",CB[i][j]);
		fprintf(fout,"\n");
	}
	fclose(fout);
}

int main()
{
	citire();
	ns=ncb=0;
	for (int i=1;i<=n;++i)
	 if (!viz[i]) biconex(0,i);
	afisare();
	return 0;
}