Cod sursa(job #238256)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 1 ianuarie 2009 14:51:14
Problema Componente biconexe Scor Ascuns
Compilator cpp Status done
Runda Marime 1.61 kb
#include <stdio.h>
#include <assert.h>
#include <vector>

using namespace std;

#define maxn 100010

int N, M;
int L, Sol;
vector <int> A[maxn], Cmp[maxn];
int G[maxn];
char U[maxn];
int Niv[maxn], Vmin[maxn], Tata[maxn];
int StivaX[maxn], StivaY[maxn], Mark[maxn];

void DFS(int nod)
{
	int i;

	U[nod] = 1;
	Vmin[nod] = Niv[nod];

	for (i = 0; i < G[nod]; i++)
		if (!U[A[nod][i]])
		{
			Niv[A[nod][i]] = Niv[nod] + 1;
			Tata[A[nod][i]] = nod;

			StivaX[++L] = nod;
			StivaY[L] = A[nod][i];

			DFS(A[nod][i]);

			Vmin[nod] = min(Vmin[nod], Vmin[A[nod][i]]);

			if (Vmin[A[nod][i]] >= Niv[nod])
			{
				Sol++;

				for (; L>=0 && (StivaX[L+1]!=nod || StivaY[L+1]!=A[nod][i]); L--)
				{
					if (Mark[StivaX[L]] != Sol) 
					{
						Mark[StivaX[L]] = Sol;
						Cmp[Sol].push_back(StivaX[L]);
					}

					if (Mark[StivaY[L]] != Sol)
					{
						Mark[StivaY[L]] = Sol;
						Cmp[Sol].push_back(StivaY[L]);
					}
				}
			}
		}
		else if (A[nod][i] != Tata[nod]) Vmin[nod] = min(Vmin[nod], Niv[A[nod][i]]);
}

int main()
{
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);

	int i, j, x, y, L;

	scanf("%d %d ", &N, &M);

	assert(2 <= N && N <= 100000);
	assert(1 <= M && M <= 200000);

	for (i = 1; i<=M; i++) 
	{
		scanf("%d %d ", &x, &y);

		assert(1 <= x && x <= N);
		assert(1 <= y && y <= N);

		A[x].push_back(y);
		A[y].push_back(x);
	}

	for (i = 1; i <= N; i++) G[i] = A[i].size();

/*	for (i = 1; i <= N; i++)
		if (!U[i]) DFS(i);*/

	DFS(1);

	printf("%d\n", Sol);

	for (i = 1; i <= Sol; i++)
	{
		L = Cmp[i].size();
		for (j = 0; j < L; j++) printf("%d ", Cmp[i][j]);
		printf("\n");
	}

	return 0;
}