Cod sursa(job #694847)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 28 februarie 2012 08:14:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

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 n, int f)
{
	int nc, fc;
	C++;
	do 
	{
		nc = S[NS].n;
		fc = S[NS].f;
		
		NS--;
		
		R[C].push_back (nc);
		R[C].push_back (fc);
	} while (n != nc && f != fc);
}

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

void afi (int b)
{
	A[0] = 0;
	for (int i = 0; i < R[b].size(); i++)
		A[++A[0]] = R[b][i];
	sort (A+1, A+A[0]+1);
	
	fo << A[1] << ' ';
	for (int i = 2; i <= A[0]; i++)
		if (A[i] != A[i-1])
			fo << A[i] << ' ';
	fo << '\n';
}

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