Cod sursa(job #476706)

Utilizator vlad.maneaVlad Manea vlad.manea Data 12 august 2010 09:51:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;

int N, T, M;
vector<int> Dfn, Low;
vector< vector<int> > Deg;
vector< set<int> > Cmp;
stack< pair<int, int> > Stk;

void read()
{
	int x, y;
	vector<int> Aux;
	ifstream fin("biconex.in");

	fin >> N >> M;
	Deg.assign(N + 1, Aux);
		
	while (M--)
	{
		fin >> x >> y;
		Deg[x].push_back(y);
		Deg[y].push_back(x);
	}

	fin.close();
}

void dfs(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])
		{
			dfs(v, u);
			Low[u] = min(Low[u], Low[v]);

			if (Dfn[u] <= Low[v])
			{
				pair<int, int> p;

				Cmp.push_back(set<int>());

				do
				{
					p = Stk.top();
					Cmp[Cmp.size() - 1].insert(p.first);
					Cmp[Cmp.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]);
		}
	}

}

void solve()
{
	Dfn.assign(N + 1, 0);
	Low.assign(N + 1, 0);
	Stk.push(pair<int, int>(-1, 1));
	dfs(1, -1);
}

void write()
{
	ofstream fout("biconex.out");

	fout << Cmp.size() << '\n';

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

		fout << '\n';
	}
}

int main()
{
	read();
	solve();
	write();
	return 0;
}