Cod sursa(job #446240)

Utilizator TabaraTabara Mihai Tabara Data 25 aprilie 2010 15:08:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.71 kb
/*
 * @ Copyright, 25.04.2010
 * Mihai Tabara
 * 325 CA
 * Bonus Lab 7
 * Time Complexity - O(N + M)
 * Language used: C++
 */

#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
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, const int);
void DF (int,int,int);

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()); /* elimin duplicatele din vector ( am inserat muchii deci vor if noduri care se repeta */
		for (j = 0; j < SOL[i].size(); ++j)
			printf ("%d ", SOL[i][j]);									/* afisez o componenta biconexa */
		printf ("\n");
	}

	return 0;
}

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 );				/* elimin din stiva toate muchiile pana la muchia (X,Y) inclusiv */
	SOL.push_back (tmp);						/* muchiile eliminate formeaza o componenta biconexa */
}

void DF (int nod, int fnod, int niv)
{
	IT it;
	level[nod] = low[nod] = niv;			/* current level, lowest level */
	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 */
	}
}