Cod sursa(job #485669)

Utilizator raduzerRadu Zernoveanu raduzer Data 19 septembrie 2010 08:38:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back
#define mp make_pair
#define x first
#define y second
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

const int MAX_N = 100001;
const int MAX_M = 200001;

int n, m, nr_sol, k;
int niv[MAX_N], str[MAX_N], p[MAX_N];
char f[MAX_N];
pair <int, int> stack[MAX_M];
vector <int> v[MAX_N], sol[MAX_N];

void df(int nod)
{
	f[nod] = 1;
	str[nod] = niv[nod];

	forit(it, v[nod])
	{
		int fiu = *it;

		if (!f[fiu])
		{
			niv[fiu] = niv[nod] + 1;
			p[fiu] = nod;

			stack[++k] = mp(nod, fiu);

			df(fiu);
			str[nod] = min(str[nod], str[fiu]);

			if (str[fiu] >= niv[nod])
			{
				++nr_sol;

				for (; stack[k] != mp(nod, fiu); --k)
				{
					sol[nr_sol].pb(stack[k].x);
					sol[nr_sol].pb(stack[k].y);
				}

				sol[nr_sol].pb(nod);
				sol[nr_sol].pb(fiu);
				--k;
			}
		}
		else if (p[nod] != fiu && niv[nod] > niv[fiu])
		{
			str[nod] = min(str[nod], niv[fiu]);
			stack[++k] = mp(nod, fiu);
		}
	}

}

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

	scanf("%d %d", &n, &m);

	for (i = 1; i <= m; ++i)
	{
		int x, y;

		scanf("%d %d", &x, &y);

		v[x].pb(y);
		v[y].pb(x);
	}

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

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

	for (i = 1; i <= nr_sol; ++i)
	{
		sort(sol[i].begin(), sol[i].end());
		sol[i].pb(0);

		for (j = 0; j < sol[i].size() - 1; ++j)
			if (sol[i][j] != sol[i][j + 1])
				printf("%d ", sol[i][j]);
		printf("\n");
	}
}