Cod sursa(job #597206)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 21 iunie 2011 13:58:51
Problema Componente biconexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 3.62 kb
#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,start=1;
int *A[100010];
int dfn[100010],low[100010];
// dfn[x]=numarul de ordine al nodului x in parcurgerea DFS a grafului
// low[x]=numarul de ordine al primului nod din parcurgerea DFS ce poate fi atins din x
//        pe un alt lant decat lantul unic din arborele partial DFS
// low[x]=min{dfn[x] , min{low[y] | y fiu al lui x} , min{dfn[y] | [x,y] muchie de intoarcere}}
int num,nrfii,vf,nrc;
// num - folosita la calcularea numarului de ordine a nodului curent in parcurgerea DFS
// nrfii = numarul de fii ai nodului start
// nrc = numarul de componente biconexe
struct Muchie{int x,y;};
Muchie S[200010];
int *com[100010]; //lista componentelor biconexe
bool afisat[100010];

void Citire()
{
	int i,x,y;
	ifstream fin("biconex.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		A[i]=(int *)realloc(A[i],sizeof(int));
		A[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		A[x][0]++;
		A[x]=(int *)realloc(A[x],(A[x][0]+1)*sizeof(int));
		A[x][A[x][0]]=y;
		A[y][0]++;
		A[y]=(int *)realloc(A[y],(A[y][0]+1)*sizeof(int));
		A[y][A[y][0]]=x;
	}
	fin.close();
}

void Initializare()
{
	int i;
	for(i=1;i<=n;i++)
	{
		com[i]=(int *)realloc(com[i],sizeof(int));
		com[i][0]=0;
	}
	for(i=1;i<=n;i++)
		dfn[i]=low[i]=-1;
	vf=0;
	//initializez stiva cu o muchie fictiva intre nodul de start si un nod fictiv -1
	S[vf].x=start;
	S[vf].y=-1;
}

void DeterminareComponentaBiconexa(int u,int x)
{
	//determina componenta biconexa a muchiei [u,x]
	Muchie p;
	int v[200000],nr=0,i,ultim;
	memset(v,0,sizeof(v));
	nrc++; //incrementez numarul componentelor biconexe
	do
	{
		p=S[vf--]; //extrag o muchie din stiva
		v[++nr]=p.x;
		v[++nr]=p.y;
	}
	while(!(p.x==u && p.y==x)); //cat timp nu gasesc muchia [u,x]
	sort(v+1,v+nr+1);
	if(nr==2)
	{
		for(i=1;i<=nr;i++)
		{
			com[nrc][0]++;
			com[nrc]=(int *)realloc(com[nrc],(com[nrc][0]+1)*sizeof(int));
			com[nrc][com[nrc][0]]=v[i];
		}
	}
	else
	{
		com[nrc][0]++;
		com[nrc]=(int *)realloc(com[nrc],(com[nrc][0]+1)*sizeof(int));
		com[nrc][com[nrc][0]]=v[1];
		ultim=v[1];
		for(i=2;i<=nr;i++)
		{
			while(v[i]==ultim && i<nr)
				i++;
			if(v[i]!=ultim)
			{
				com[nrc][0]++;
				com[nrc]=(int *)realloc(com[nrc],(com[nrc][0]+1)*sizeof(int));
				com[nrc][com[nrc][0]]=v[i];
				ultim=v[i];
			}
		}
	}
}

void Biconex(int u,int tu)
{
	// u este nodul curent , iar tu este nodul parinte al lui u
	int x,i;
	num++;
	dfn[u]=low[u]=num; //low[u] este si el initial numarul de ordine al lui u
	//parcurg lista de adiacenta a nodului u
	for(i=1;i<=A[u][0];i++)
	{
		x=A[u][i]; //x este nod adiacent cu u
		if(x!=tu && dfn[x]<dfn[u])
		{
			//inserez muchia [u,x] in stiva
			vf++;
			S[vf].x=x;
			S[vf].y=u;
		}
		if(dfn[x]==-1) //nodul x nu a mai fost vizitat
		{
			if(u==start) //am gasit un fiu al nodului start
				nrfii++;
			Biconex(x,u);
			low[u]=min(low[u],low[x]);
			if(low[x]>=dfn[u]) //nodul u este punct de articulatie
			{
				//am gasit o componenta biconexa
				//formata din muchiile din stiva pana la intalnirea muchiei [u,x]
				DeterminareComponentaBiconexa(x,u);
			}
		}
		else //nodul x a mai fost vizitat
		{
			if(x!=tu) //daca x nu este tatal lui u
			{
				//atunci [u,x] este muchie de intoarcere de la u la x
				low[u]=min(low[u],dfn[x]);
			}
		}
	}
}

int main()
{
	int i,j;
	Citire();
	Initializare();
	Biconex(start,-1);
	ofstream fout("biconex.out");
	fout<<nrc<<"\n";
	for(i=1;i<=nrc;i++)
	{
		for(j=1;j<=com[i][0];j++)
			fout<<com[i][j]<<' ';
		fout<<"\n";
	}
	fout.close();
	return 0;
}