Cod sursa(job #650998)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 19 decembrie 2011 16:11:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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, NB, NS, niv[dim], low[dim];
struct { int n, f; } S[dim<<1];
vector <int> B[dim<<1], 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 bico (int ns, int fs)
{
	int n, f;
	NB++;
	do 
	{
		n = S[NS].n;
		f = S[NS].f;
		
		B[NB].push_back (S[NS].n);
		B[NB].push_back (S[NS].f);
		
		--NS;
	} while ( !(n == ns && f == fs) );	
}

void dfs (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)
		{
			++NS;
			S[NS].n = n;
			S[NS].f = f;
			dfs (f, n);
			low[n] = min (low[n], low[f]);
			if (niv[n] <= low[f])
				bico (n, f);
		}
		else
			low[n] = min (low[n], niv[f]);
	}	
}

void afi ()
{
	fo << NB << '\n';
	for (int i = 1; i <= NB; i++)
	{
		sort (B[i].begin(), B[i].end());
		fo << B[i][0] << ' ';
		for (int j = 1; j < B[i].size(); j++)
			if (B[i][j] != B[i][j-1])
				fo << B[i][j] << ' ';
		fo << '\n';
	}
}

int main ()
{
	cit ();
	dfs (1, 0);
	afi ();
	
	return 0;
}