Cod sursa(job #478560)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 19 august 2010 10:16:54
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<fstream>
#include<vector>
#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);
	}
}

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;
	for(int i=0; i<LA[u].size(); i++)
	{
		int 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 if( x!=tu ) // a mau fist vizitat => muchie inapoi
			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];
		for(int j=0; i<v.size(); j++) g<< v[j] <<" ";
		g<<"\n";
	}
}

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