Cod sursa(job #296128)

Utilizator raduzerRadu Zernoveanu raduzer Data 4 aprilie 2009 12:16:02
Problema Componente biconexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <vector>
using namespace std;

const int MAX_N = 1010;
const int nod_s = 1;

int n, m, z, k, sol;
int niv[MAX_N], f[MAX_N], par[MAX_N], c[MAX_N], scris[MAX_N], noduri[MAX_N];
int st1[MAX_N], st2[MAX_N];
vector <int> v[MAX_N];
int s[MAX_N][MAX_N];

void checkMin(int &a, int b)
{
	if (a > b) a = b;
}

void df(int nod)
{
	f[nod] = 1;
	c[nod] = niv[nod];
	
	for (int i = 0; i < v[nod].size(); ++i)
	{
		int fiu = v[nod][i];
		
		if (!f[fiu])
		{
			par[fiu] = nod;
			niv[fiu] = niv[nod] + 1;
			

			st1[++k] = nod;
			st2[k] = fiu;
			
			df(fiu);
			checkMin(c[nod], c[fiu]);
			
			if (c[fiu] >= niv[nod])
			{
				++sol;
//				printf("%d\n", sol);
				while (!(st1[k] == nod && st2[k] == fiu)) 
				{
					s[sol][st1[k]] = 1;
					s[sol][st2[k]] = 1;
					--k;
				}
				s[sol][st1[k]] = s[sol][st2[k]] = 1;
				--k;
			}
		}
		else 
		if (par[nod] != fiu && niv[fiu] < niv[nod])
		{
			checkMin(c[nod], niv[fiu]);
			st1[++k] = nod;
			st2[k] = fiu;
		}
	}
}

int main()
{
	int i, x, y;
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i = 1; i <= m; ++i)
	{
		scanf("%d %d", &x, &y);
		
		v[x].push_back(y);
		v[y].push_back(x);
	}

	niv[nod_s] = 1;
	df(nod_s);

	printf("%d\n", sol);
	for (i = 1; i <= sol; ++i)
	{
		for (int j = 1; j <= n; ++j)
			if (s[i][j] == 1) printf("%d ", j);
		printf("\n");
	}
}