Cod sursa(job #288866)

Utilizator gggbbbyyyDarkMan gggbbbyyy Data 26 martie 2009 10:12:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.06 kb
#include <fstream.h>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

struct lista
{
	long nod;
	lista *urm;
};

struct l2
{	/*lista dublu inlantuita: prec = pointer spre nodul precedent, urm = spre urmator*/
	long x, y;
	l2 *urm,*prec;
};
const int nmax = 100005;
const int nmax2 = 200005;
long n, m, tata[nmax], l[nmax], nivel[nmax], nr,biconexa[nmax];
lista *a[nmax2];
l2 *s, *sol[nmax2];

//******************LISTELE DE VECINI

//pun y in lista de vecini a lui x

void adaug_vecin(long x, long y)
{
	lista *p;

	p=new lista;
	p->nod=y;
	p->urm=NULL;

	if (a[x])
		p->urm=a[x];

	a[x]=p;
}

//************************CONSTRUIREA SOLUTIEI  sol[nr]=inceputul unei liste care retine solutia nr

//adaug la solutie muchia (x,y)
void adaug_sol(long x, long y)
{
	l2 *d;

	d=new l2;
	d->x=x;
	d->y=y;

	d->urm=0;
	d->prec=0;

	if (sol[nr]!=0)
	{
		d->prec=sol[nr];
		sol[nr]->urm=d;
	}

	sol[nr]=d;
}

//************************ELIMINAM O MUCHIE DIN STIVA S

// !!!!!!!!!!!!!!!!!!!!!!TRANSIMTEM CE AM ELIMINAT(VALOAREA LUI X SI Y)!!!!!!!!!!!!
//elimin muchia (x,y) din stiva
void elimin(long *x, long *y)
{
	l2 *d;

	d=new l2;

	*x=s->x;
	*y=s->y;

	d=s;

	s=s->prec;
	delete d;
}

//**************************ADAUGAM ELEMENTE IN STIVA S

void adaug_stiva(long x, long y)
{
	l2 *d;
	d=new l2;

	d->x=x;
	d->y=y;
	d->urm=NULL;//ambii pointeri (campuri de legatura)
	d->prec=NULL;  //ii initializez cu NULL

	//adaug nodul d
	if (s!=0) //daca s nu are elemente se va executa doar atribuirea s=d
	{
		d->prec=s;
		s->urm=d;
	}
	s=d;
}

//*********************PARCURGEREA IN ADANCIME

//parcurgerea in adancime
void df(long k)
{
	lista *p;
	l2 *d;
	long x,y;

	l[k]=nivel[k];//initializez nivelul de care pot ajunge de la nodul k
	//chiar cu nivelul pe care se afla in cazul parcurgerii df

	for (p=a[k];p!=0;p=p->urm)  //parcurg lista de vecini a lui k
		//  am declarat : "lista *a[nmax2];"

		if (!tata[p->nod])  //daca nu este adaugat deja
		{
			adaug_stiva(k,p->nod);
			tata[p->nod]=k;
			nivel[p->nod]=nivel[k]+1;

			df(p->nod);  // functia se va autoapela fara a trece mai departe

			// !!!!!!!!!!!!!!!instructiunile de mai jos se vor executa dar doar dupa ce se termina
			//apelurile recursive df(p->nod) deci practic dupa ce sunt construiti vectorii: l,nivel,tata!!!!!!!

			if (l[p->nod]<l[k]) l[k]=l[p->nod];//actualizez nivelul pe care pot ajunge din nodul k

			if (l[p->nod]>=nivel[k])  //daca din p->nod nu pot ajunge mai sus de k
			{
				nr++;                 //am gasit o comp biconexa
				do
				{
					elimin(&x,&y); //elimin muchie. x si y vor primi valori din functia elimin (ult element din stiva s)
					adaug_sol(x,y);//adaug muchia la solutie
				}
				//pana cand stiva este goala sau am ajuns la muchia (k,p->nod)
				while (s && (x!=k || y!=p->nod) && (x!=p->nod || y!=k));
			}
		}
		else
			if (p->nod!=tata[k] && nivel[p->nod]<l[k]) //daca p->nod nu este taticul lui k
				l[k]=nivel[p->nod];         //si nivelul  lui p->nod in cadrul parcurgeri df este mai mic decat nivelul pe
	//care pot ajunge de la k atunci actualizez nivelul pe care pot ajunge de la k cu
	//nivelul lui p->nod in cazul parcurgerii df
}

//**********main

int main()
{
	long i,p1,p2,x,y;
	f>>n>>m;  //citirea din fisier si adaugarea muchiilor
	for (i=1;i<=m;i++)
	{
		f>>p1>>p2;
		adaug_vecin(p1,p2);
		adaug_vecin(p2,p1);
	}

//apelez parcurgerea in adancime df pentru fiecare nod
//daca graful este conex atunci df se apeleaza o singura data
//daca nu este conex se apeleaza pt fiecare componenta conexa
	for (i=1;i<=n;i++)
		if (!tata[i])
		{
			tata[i]=-1;
			nivel[i]=1;
			df(i);
		}

	g<<nr<<'\n';

	//avem nr componente biconexe
	for (i=1;i<=nr;i++)
	{
		do
		{
			y=sol[i]->y;
			x=sol[i]->x;

			if (biconexa[x]!=i)
			{
				g<<x<<" ";
				biconexa[x]=i;
			}

			if (biconexa[y]!=i)
			{
				g<<y<<" ";
				biconexa[y]=i;
			}

			sol[i]=sol[i]->prec;
		}
		while (sol[i]);
		g<<'\n';
	}

	g.close();
	return 0;
}