Cod sursa(job #530300)

Utilizator ilincaSorescu Ilinca ilinca Data 7 februarie 2011 14:41:14
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define nmax 100005
#define pb push_back

using namespace std;

int n, m, ncomp, k, niv [nmax], c [nmax], tata [nmax];
bool viz [nmax];
vector <int> g [nmax];
vector <int> comp [nmax];
pair <int, int> stiva [nmax];

void scan ()
{
	int i, a, b;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d", &a, &b);
		g [a].pb (b);
		g [b].pb (a);
	}
}

inline int min (int a, int b)
{
	if (a < b)
		return a;
	return b;
}

void dfs (int nod)
{
	int i, fiu;
	viz [nod]=true;
	c [nod]=niv [nod];
	for (i=0; i != g [nod].size (); ++i)
	{
		fiu=g [nod] [i];
		if (viz [fiu])
		{
			if ((tata [fiu] != nod) && (niv [nod] > niv [fiu]))
			{
				c [nod]=min (c [nod], niv [fiu]);
				stiva [++k]=make_pair (nod, fiu);
			}
			continue;
		}
		niv [fiu]=niv [nod]+1;
		tata [fiu]=nod;
		stiva [++k]=make_pair (nod, fiu);
		dfs (fiu);
		c [nod]=min (c [nod], c [fiu]);
		if (c [fiu] >= niv [nod])
		{
			++ncomp;
			while (stiva [k] != make_pair (nod, fiu))
			{
				comp [ncomp].push_back (stiva [k].first);
				--k;
			}
			comp [ncomp].push_back (stiva [k+1].second);
			comp [ncomp].push_back (nod);
			comp [ncomp].push_back (fiu);
			--k;
		}
		
	}
}

void print ()
{
	int i;
	vector <int> :: iterator it, j;
	printf ("%d\n", ncomp);
	for (i=1; i <= ncomp; ++i)
	{
		sort (comp [i].begin (), comp [i].end ());
		it=unique (comp [i].begin (), comp [i].end ());
		for (j=comp [i].begin (); j != it; ++j)
			printf ("%d ", *j);
		printf ("\n");
	}		
}

int main ()
{
	freopen ("biconex.in", "r", stdin);
	freopen ("biconex.out", "w", stdout);
	scan ();
	niv [1]=1;
	dfs (1);
	print ();
	return 0;
}