Cod sursa(job #476579)

Utilizator vlad.maneaVlad Manea vlad.manea Data 11 august 2010 17:12:18
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.41 kb
#ifndef _ALGORITHM_H
#define _ALGORITHM_H
#include <fstream>
using namespace std;

/**
	Algorithm abstract class
	specifies protocol
*/
template<class I, class O>
class Algorithm
{
protected:

	I &in;
	O &out;

	/**
		algorithm method
		instantiates i/o
	*/
	Algorithm(I &, O &);
};

/**
	algorithm method
	instantiates i/o
*/
template<class I, class O>
Algorithm<I, O>::Algorithm(I &inp, O &outp): in(inp), out(outp)
{

}

#endif


#ifndef _BICONNECTIVITY_H
#define _BICONNECTIVITY_H

#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;

/**
	Biconnectivity class
	solves the connectivity in a graph problem
*/
class Biconnectivity: public Algorithm< vector<int>, pair< vector<int>, vector< set<int> > > >
{
	int N, T, S;
	vector<int> Dfn, Low;
	vector< vector<int> > Deg;
	stack< pair<int, int> > Stk;

public:

	/**
		biconnectivity method
		runs algorithm
	*/
	Biconnectivity(vector<int> &, pair< vector<int>, vector< set<int> > > &);

private:

	/**
		read method
		reads input
	*/
	void Read();

	/**
		solve method
		solves problem
	*/
	void Solve();

	/**
		bidfs method
		computes biconnectivity
	*/
	void BiDFS(int, int);
};

#endif


/**
	biconnectivity method
	runs algorithm
*/
Biconnectivity::Biconnectivity(vector<int> &in, pair< vector<int>, vector< set<int> > > &out): 
	Algorithm< vector<int>, pair< vector<int>, vector< set<int> > > >(in, out), N(0), S(0), T(0)
{
	Read();
	Solve();
}

/**
	read method
	reads input
*/
void Biconnectivity::Read()
{
	int x, y, c, m;
	vector<int> Aux1;

	N = in[0];
	m = in[1];

	for (c = 0; c <= N; ++c)
	{
		Deg.push_back(Aux1);
	}
		
	for (c = 0; c < m; ++c)
	{
		x = in[c * 2 + 2];
		y = in[c * 2 + 3];
		Deg[x].push_back(y);
		Deg[y].push_back(x);
	}
}

/**
	solve method
	solves problem
*/
void Biconnectivity::Solve()
{
	Dfn.assign(N + 1, 0);
	Low.assign(N + 1, 0);
	Stk.push(pair<int, int>(-1, 1));
	BiDFS(1, -1);
	
	if (S >= 2)
	{
		out.first.push_back(1);
	}
}

/**
	bidfs method
	computes biconnectivity
*/
void Biconnectivity::BiDFS(int u, int t)
{
	int v;

	Dfn[u] = Low[u] = ++T;

	for (vector<int>::iterator i = Deg[u].begin(); i != Deg[u].end(); ++i)
	{
		v = *i;

		if (v != t && Dfn[v] < Dfn[u])
		{
			Stk.push(pair<int, int>(u, v));
		}

		if (!Dfn[v])
		{
			if (u == 1)
			{
				++S;
			}

			BiDFS(v, u);
			Low[u] = min(Low[u], Low[v]);

			if (Dfn[u] <= Low[v])
			{
				if (u != 1)
				{
					out.first.push_back(u);
				}

				pair<int, int> p;

				out.second.push_back(set<int>());

				do
				{
					p = Stk.top();
					out.second[out.second.size() - 1].insert(p.first);
					out.second[out.second.size() - 1].insert(p.second);
					Stk.pop();
				}
				while(p.first != u || p.second != v);
			}
		}
		else if (v != t)
		{
			Low[u] = min(Low[u], Low[v]);
		}
	}
}

int main()
{
	ifstream fin("maxflow.in");
	ofstream fout("maxflow.out");
	int N, M, x, y;

	vector<int> I;
	pair< vector<int>, vector< set<int> > > O;

	fin >> N >> M;
	I.push_back(N);
	I.push_back(M);

	while (M--)
	{
		fin >> x >> y;
		I.push_back(x);
		I.push_back(y);
	}

	Biconnectivity mflow(I, O);

	fout << O.second.size() << '\n';

	for (vector< set<int> >::iterator i = O.second.begin(); i != O.second.end(); ++i)
	{
		for (set<int>::iterator j = i->begin(); j != i->end(); ++j)
		{
			fout << *j << ' ';
		}

		fout << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}