Cod sursa(job #1140097)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 11 martie 2014 18:55:40
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<stack>
#define pb push_back
using namespace std;
vector <int> gr[100001];
vector <int> cbc[200001];
stack <pair <int, int> > com;
int ncbc;
bool viz[100001];
int niv[100001];
void dfs(int vf, int tata, int nivel)
{
	int i,nivi=nivel;
	int lim=gr[vf].size();
	viz[vf]=1;
	niv[vf]=nivel;
	for(i=0;i<lim;i++)
	{
		if(!viz[gr[vf][i]])
		{
			com.push(make_pair(vf,gr[vf][i]));
			dfs(gr[vf][i],vf,nivel+1);
			if(niv[gr[vf][i]]>=nivel)
			{
				ncbc++;
				while((com.top().first!=vf)||(com.top().second!=gr[vf][i]))
				{
					cbc[ncbc].pb(com.top().second);
					com.pop();
				}
				cbc[ncbc].pb(com.top().second);
				cbc[ncbc].pb(com.top().first);
				com.pop();
			}
		}
		if(gr[vf][i]!=tata)
			nivi=min(nivi,niv[gr[vf][i]]);
	}
	niv[vf]=nivi;
}
int main()
{
	int n,m;
	int x,y;
	int i,j;
	int lim;
	ifstream f("biconex.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		gr[x].pb(y);
		gr[y].pb(x);
	}
	f.close();
	for(i=1;i<=n;i++)
		if(!viz[i])
			dfs(i,0,1);
	ofstream g("biconex.out");
	g<<ncbc<<'\n';
	for(i=1;i<=ncbc;i++)
	{
		lim=cbc[i].size();
		for(j=0;j<lim;j++)
			g<<cbc[i][j]<<' ';
		g<<'\n';
	}
	g.close();
	return 0;
}