Cod sursa(job #662215)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 16 ianuarie 2012 08:21:00
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fi ("biconex.in");
ofstream fo ("biconex.out");

const int dim = 100005;
struct muc { int n, f; } S[dim];
vector <int> B[dim], V[dim];
int N, M, C, niv[dim], low[dim], NS;

void cit ()
{
	fi >> N >> M;
	for (int i = 1, x, y; i <= M; i++)
	{
		fi >> x >> y;
		V[x].push_back (y);
		V[y].push_back (x);
	}
}

void gasit (int n1, int f1)
{
	int n, f;
	++C;
	do 
	{
		n = S[NS].n;
		f = S[NS].f;
		B[C].push_back (n);
		B[C].push_back (f);
		NS--;
	} while (n != n1 && f != f1);
	
	sort (B[C].begin(), B[C].end());
	for (int i = 1, j = 1; i < B[C].size(); i++)
		if (B[C][i] != B[C][i-1])
			B[C][++j] = B[C][i];
}

void bic (int n, int k)
{
	niv[n] = low[n] = k;
	
	for (int i = 0, f; i < V[n].size(); i++)
	{
		f = V[n][i];
		if (niv[f] == 0)
		{
			++NS;
			S[NS].n = n;
			S[NS].f = f;
			
			bic (f, k + 1);
			
			low[n] = min (low[f], low[n]);
			if (low[f] <= niv[n])
				gasit (n, f);
		}
		else
		{
			low[n] = min (low[f], niv[n]);
		}	
	}
	
	
}

void afi ()
{
	fo << C << '\n';
	for (int i = 1, j; i <= C; i++)
	{
		for (j = 0; j < B[i].size(); j++)
			fo << B[i][j] << ' ';
		fo << '\n';
	}	
}

int main ()
{
	cit ();
	for (int i = 1; i <= N; i++)
		if (niv[i] == 0)
			bic (i, 1);
	afi ();
	return 0;
}