Cod sursa(job #383486)

Utilizator raduzerRadu Zernoveanu raduzer Data 16 ianuarie 2010 18:01:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define pdd pair<double, double>
#define pid pair<int, double>
#define pdi pair<double, int>
#define ppi pair<pair<int, int>, int>
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
#define sz(v) v.size()
#define del(it, v) v.erase(it)
#define db double
#define ll long long

const int INF = 0x3f3f3f3f;
const int MAX_N = 100010;
const int MAX_M = 0;
const int MAX_L = 0;

int n, m, z, sol;
int f[MAX_N], c[MAX_N], niv[MAX_N], p[MAX_N];
pii q[MAX_N * 2];
vector <int> v[MAX_N], s[MAX_N];

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

	forit(it, v[nod])
		if (!f[*it])
		{
			p[*it] = nod;
			niv[*it] = niv[nod] + 1;

			q[++z] = mp(nod, *it);

			df(*it);

			c[nod] = min(c[nod], c[*it]);

			if (c[*it] >= niv[nod])
			{
				++sol;

				do {
					s[sol].pb(q[z].x);
					s[sol].pb(q[z].y);
					--z;
				} while (mp(nod, *it) != q[z + 1]);
			}
		}
		else if (p[nod] != *it && niv[*it] < niv[nod])
		{
			c[nod] = min(c[nod], niv[*it]);
			q[++z] = mp(nod, *it);
		}
}

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

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

	for (i = 1; i <= m; ++i)
	{
		int r1, r2;

		scanf("%d %d", &r1, &r2);

		v[r1].pb(r2);
		v[r2].pb(r1);
	}

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

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

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

		s[i].pb(INF);

		forit(it, s[i])
			if (*it != *(it + 1) && *it != INF)
				printf("%d ", *it);
		printf("\n");
	}
}