Cod sursa(job #446219)

Utilizator TabaraTabara Mihai Tabara Data 25 aprilie 2010 14:32:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const char *in = "biconex.in";
const char *out = "biconex.out";
const int DIM = 2800000;
const int NMAX = 100005;

typedef vector<int>::iterator IT;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;

template <class T>
T minim (T a, T b)
{
	return ((a) < (b) ? (a) : (b));
}

int N, M;
VI L[NMAX], level, low;
VVI SOL;
stack< pair<int,int> > st;

void Push( const int X, const int Y)
{
	VI tmp;
	int x, y;
	do
	{
		x = st.top().first, y = st.top().second;
		st.pop();
		tmp.push_back(x), tmp.push_back(y);
	} while (x != X || y != Y );
	SOL.push_back (tmp);
}

void DF( int nod, int fnod, int niv)
{
	IT it;
	level[nod] = low[nod] = niv;
	for ( it = L[nod].begin(); it != L[nod].end(); ++it)
	{
		if (*it == fnod) continue;
		if (level[*it] == -1)		/* muchie de arbore */
		{
			st.push(make_pair (nod, *it));
			DF (*it, nod, niv+1);
			low[nod] = minim( low[nod], low[*it]);
			if (low[*it] >= level[nod] )	/* nod - punct de articulatie */
				Push( nod, *it);
		}
		else
			low[nod] = minim( low[nod], level[*it]);	/* muchie de intoarcere */
	}
}

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

	char buf[DIM];
	int X, Y, poz;
	/* Parsing the input reading */

	fread (buf, 1, DIM, stdin);
	#define cit(x)											\
	{														\
		x = 0;												\
		while (buf[poz] < '0')								\
		{													\
			++poz;											\
			if (poz == DIM) {								\
				fread (buf, 1, DIM, stdin); poz = 0; }		\
		}													\
		while (buf[poz] >= '0')								\
		{													\
			x = x*10 + buf[poz] - '0';						\
			if (++poz == DIM) {								\
				fread (buf, 1, DIM, stdin); poz = 0; }		\
		}													\
	}
	cit(N) cit(M)
	for ( ; M; --M)
	{
		cit(X) cit(Y)
		L[X].push_back (Y);
		L[Y].push_back (X);
	}
	level.resize( N + 1 );
	level.assign( N + 1, -1);
	low.resize (N+1);

	DF(1,0,0);
	size_t i = SOL.size(), j;
	printf ("%d\n", i);
	for (i = 0; i < SOL.size(); ++i)
	{
		sort(SOL[i].begin(), SOL[i].end());
		SOL[i].erase(unique(SOL[i].begin(), SOL[i].end()), SOL[i].end());
		for (j = 0; j < SOL[i].size(); ++j)
			printf ( "%d ", SOL[i][j]);
		printf ("\n");
	}

	return 0;
}