Cod sursa(job #256969)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 12 februarie 2009 16:38:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4 kb
#include<stdio.h>

#define infile "biconex.in"
#define outfile "biconex.out"

#define nmax (100*1000+1)
#define mmax (300*1000+1)

#define start 1 //nodul de start din care vom face aprcurgerea

int save[mmax], nrpos, nrcom; //vectorul in care salvam componentele biconexe,, variabila cu pozitiile ocupate de componente,  si variabila in care salvam numarul lor
int viz[nmax]; //v[i] - ultima componenta biconexa in care a fost bagat nodul i

struct lista
	{
	int n,p; //nodul, respectiv pozitia din lista a lu frasu
	} l[mmax];
struct nod
	{
	int p; //pozitia din lista a ultimului fiu
	int nr; //numarul de ordine din parcurgerea dfs
	int nrt; //numarul minim de ordine al unui stramos din parcurgerea dfs (!tata)
	} p[nmax];
struct stiva
	{
	int t,f; //muchia de la tata la fiu :P
	} s[mmax];
int nro; //numarul de ordine al nodurilor in parcurgere
int st; //numarul de elemente din stiva
int n; //numarul de noduri

//adaugam arcul (x,y)
void add(struct lista l[mmax], struct nod p[nmax], int m, int x, int y)
	{
	l[m].n=y; l[m].p=p[x].p; p[x].p=m;
	}

void citire(struct lista l[mmax], struct nod p[nmax], int *n)
	{
	int m,x,y,i,j;
	scanf("%d %d\n",n,&m);
	for(j=0,i=1;i<=m;i++) //citim fiecare muchie :P
		{
		scanf("%d %d\n",&x,&y);
		add(l,p,++j,x,y);
		add(l,p,++j,y,x);
		}
	}

void initializare(struct lista l[mmax], struct nod p[nmax], struct stiva s[mmax], int *st, int n)
	{
	int i;
	for(i=1;i<=n;i++) p[i].nr=p[i].nrt=-1; //initial nu au fost atinse punctele in parcurgere :P
	*st=0; s[0].t=-1; s[0].f=start; //adaugam o muchie fictiva catre nodul de start :P
	}

//salveaza componenta in vectorul global save[]
void salveaza_componenta(struct stiva s[mmax], int *st, int u, int x)
	{
	struct stiva pct;
	nrcom++; //am gasit o componenta biconexa
	do { 
		pct=s[*st]; *st-=1;
		if(viz[pct.f]!=nrcom) { save[++nrpos]=pct.f; viz[pct.f]=nrcom; } //salvam nodul daca nu a mai fost salvat
		if(viz[pct.t]!=nrcom) { save[++nrpos]=pct.t; viz[pct.t]=nrcom; } //salvam nodul daca nu a mai fost salvat
		}
	while(pct.t!=u || pct.f!=x );
	save[++nrpos]=0; //sa stim ca am marcat o componenta biconexa
	}

//parcurgere in inaltime facuta a.i. sa afla componentele biconexe (din nodul u, cu tatal ut)
void dfs(struct lista l[mmax], struct nod p[nmax], struct stiva s[mmax], int *st, int u, int ut)
	{
	p[u].nr=p[u].nrt=++nro; //punem numarul de ordine....
	int x,ul=p[u].p; //aici vom avea pozitia din lista a fiilor lui u
	while(ul) //cat timp u mai are copii
		{
		x=l[ul].n; //copilul lui u
		if(x!=ut && p[x].nr<p[u].nr) //daca copilul nu e defapt tatal, si daca copilul este defapt un stramos sau nu a mai fost vizitat
			{ *st+=1; s[*st].t=u; s[*st].f=x; } //adaugam muchia in stiva
		if(p[x].nr==-1) //acest nod nu a mai fost vizitat...
			{
			dfs(l,p,s,st,x,u); //parcurgem nodul :P
			if(p[x].nrt<p[u].nrt) p[u].nrt=p[x].nrt; //daca copilul lui u poate ajunge la un stramos mai invarsta (cu numarul de ordine cat mai mic)
			if(p[x].nrt>=p[u].nr) //u este nod de articulatie
				salveaza_componenta(s,st,u,x); //salvam componenta biconexa, si o scoatem din stiva:P
			}
		else if(x!=ut) //daca a mai fost vizitat, si daca nu este tatal nodului
			if(p[u].nrt>p[x].nr) p[u].nrt=p[x].nr; //fiind deja vizitat, si nefiind tata, inseamna ca este stramos....daca este cel mai inalt nod ce poate fi atins (nr ordine mic), salvam asta :P
		ul=l[ul].p; //trecem la un alt copil al nodului u
		}
	}

void afisare(int save[mmax], int nrpos, int nrcom)
	{
	int i;
	printf("%d\n",nrcom);
	for(i=1;i<=nrpos;i++)
		if(!save[i]) printf("\n"); //am terminat de afisat o componenta biconexa
		else printf("%d ",save[i]);
	}

int main()
{
 freopen(infile,"r",stdin);
 freopen(outfile,"w",stdout);

citire(l,p,&n); //citim datele din fisier
initializare(l,p,s,&st,n); //facem initializarea nodurilor si a stivei
dfs(l,p,s,&st,start,-1); //parcurgem graful din nodul start...pt a afla numarul de componente biconexe
afisare(save,nrpos,nrcom);

fclose(stdin);
fclose(stdout);
return 0;
}