Cod sursa(job #712181)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 13 martie 2012 09:21:36
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int i,n,m,a,b,nr,sol,cd[200001],aux;
bool viz[100001];
vector <int> v[100001];
vector <int> rasp[100001];
inline void df(int k,int par)
{   vector <int>::iterator it;
	for (it=v[k].begin();it!=v[k].end();++it)
		if (!viz[*it])
		{   viz[*it] = true;
		    cd[++nr] = *it;
			df(*it,k);
        }
	    else
		    if (*it != par)
			{	++sol;
				while (*it != cd[nr])
		     	{	rasp[sol].push_back(cd[nr]);
			    	--nr;
		     	}
		        rasp[sol].push_back(*it);
				v[*it].erase(find(v[*it].begin(),v[*it].end(),k));
			}
}
int main()
{   fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> a >> b;
	    v[a].push_back(b);
		v[b].push_back(a);
	}
	viz[1] = true;
	cd[++nr] = 1;
	df(1,0);
	vector <int>::iterator it;
	++nr;
	for (i=1;i<=nr/2;++i)
	{	++sol;
		rasp[sol].push_back(cd[i]);
		rasp[sol].push_back(cd[i+1]);
	}
	if (nr % 2 != 0)
	{   ++sol;
		rasp[sol].push_back(cd[nr]);
	}
	fout << sol << '\n';
	for (i=1;i<=sol;++i)
	{   for (it=rasp[i].begin();it!=rasp[i].end();++it)
			fout << *it << " " ;
	    fout << '\n';
	}
	return 0;
}