Cod sursa(job #530333)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 7 februarie 2011 16:19:11
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100001;
const int M = 200001;

struct muchie
{
	int a,b;
};

int n;
vector<int> vecin[N];
bool vizitat[N];
int tata[N];
muchie stiva[M];int nstiva;
vector<int> sol[N]; int nsol;
int c[N],niv[N];

void citire()
{
	int a,b,m;
	scanf("%i%i",&n,&m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%i%i",&a,&b);
		vecin[a].push_back(b);
		vecin[b].push_back(a);
	}
}

void dfs(int nod)
{
	vizitat[nod] = true;
	c[nod] = niv[nod]; //c[i] -> nivelul cel mai de sus (minima) la care pot ajunge din subarborele lui i
	for (int i = 0; i < vecin[nod].size(); ++i)
	{
		int fiu = vecin[nod][i];
		if (!vizitat[nod])
		{
			tata[fiu] = nod;
			niv[fiu] = niv[nod] + 1;
			stiva[++nstiva].a = nod;
			stiva[nstiva].b = fiu;
			
			dfs(fiu);
			
			if (c[nod] > c[fiu])
				c[nod] = c[fiu];			
			
			//am gasit o componenta biconexa
			if (niv[nod] <= c[fiu])
			{
				++nsol;
				while (!(stiva[nstiva].a == nod && stiva[nstiva].b == fiu))
				{
					sol[nsol].push_back(stiva[nstiva].a);
					sol[nsol].push_back(stiva[nstiva].b);
					--nstiva;
				}
				sol[nsol].push_back(stiva[nstiva].a);
				sol[nsol].push_back(stiva[nstiva].b);
				--nstiva;
			}
		}
		else
			if (tata[nod] != fiu && niv[fiu] < niv[nod])
			{
				if (c[nod] > niv[fiu])
					c[nod] = niv[fiu];
				stiva[++nstiva].a = nod;
				stiva[nstiva].b = fiu;
			}
	}
}

void afisare()
{
	printf("%i\n",nsol);
	for (int i = 1; i <= nsol; ++i)
	{
		sort(sol[i].begin(),sol[i].end());
		for (int j = 0; j < sol[i].size(); ++j)
			if ((j < sol[i].size() - 1 && sol[i][j] != sol[i][j + 1]) || j == sol[i].size() - 1)
				printf("%i ",sol[i][j]);
		printf("\n");
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	citire();
	dfs(1);
	afisare();
	return 0;
}