Cod sursa(job #478563)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 19 august 2010 10:34:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define inf "biconex.in"
#define outf "biconex.out"
#define NMax 100100
#define MMax 200100
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

struct muchie { int t,f; } St[MMax]; int VfSt;

int N,M;
const int start = 1;

vector<int> LA[NMax];
vector< vector<int> > bc;
int nr,nrc,nrf;
int dfn[NMax],low[NMax],art[NMax];

void read()
{
	int a,b;
	f>>N>>M;
	for(int i=1; i<=M; i++)
	{
		f>>a>>b;
		LA[a].push_back(b);
		LA[b].push_back(a);
	}
}

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

void cache_bc(int x,int u)
{
	vector<int> v; muchie p;
	nrc++;
	do
	{
		p = St[VfSt--];
		v.push_back(p.t); v.push_back(p.f);
	}
	while( p.t!=u || p.f!=x );
	bc.push_back( v );
}

void biconex(int u,int tu)
{
	dfn[u] = low[u] = ++nr;
	int x,i;
	for(i=0; i<LA[u].size(); i++)
	{
		x = LA[u][i];

		if( x!=tu && dfn[x]<dfn[u] ) { St[++VfSt].t = u ; St[VfSt].f = x; }

		if( dfn[x]==-1 ) //nu a mai fost vizitat
		{
			if( u==start ) nrf++;
			biconex(x,u);
			low[u] = min(low[u],low[x]);
			if( low[x] >= dfn[u] )
			{
				if( u!=start ) art[u] = 1;
				cache_bc(x,u);
			}
		}
		else // a mai fost vizitat => muchie inapoi
		{
			if( x!=tu ) low[u] = min(low[u],dfn[x]);
		}
	}
}

void solve()
{
	//Init
	for(int i=1; i<=N; i++) dfn[i] = low[i] = -1;
	St[VfSt].f = start; St[VfSt].t = -1;

	//Solve
	biconex(start,-1);
	if( nrf>1 ) art[start] = 1;
	g<< nrc <<"\n";
	for(int i=0; i<bc.size(); i++)
	{
		vector<int> v = bc[i];
		sort( v.begin(), v.end() );
		for(int j=0; j<bc[i].size(); j++)
			if( j!=0 && v[j]!=v[j-1] ) g<< v[j] <<" ";
			else if( !j ) g<< v[j] <<" ";
		g<<"\n";
	}
}

int main()
{
	read();
	solve();
	f.close();
	g.close();
	return 0;
}