Cod sursa(job #499239)

Utilizator marius21Petcu Marius marius21 Data 9 noiembrie 2010 11:12:15
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <cstdio>
#include <cstdlib>
#include <list>
using namespace std;

FILE *fin=fopen("biconex.in","r");
FILE *fout=fopen("biconex.out","w");


bool bif[100000];

struct muchie;

struct el2
{
	int v;
	muchie * m;
};


struct muchie
{
	int x,y;
	list<el2>::iterator xi,yi;
};

list<el2> v[100000];

struct el
{
	int e,t;
	list<el2>::iterator it;
};

list<el> q;
list<list<int> > res;
list<int> qq;

int main (int argc, char * const argv[]) {
	int n,m;
	fscanf(fin, "%d%d",&n,&m);
	for (int i=0; i<m ; i++)
	{
		int x,y;
		fscanf(fin, "%d%d",&x,&y);
		x--; y--;
		el2 tmp;
		tmp.v=y;
		v[x].push_back(tmp);
		tmp.v=x;
		v[y].push_back(tmp);
		muchie * m = new muchie;
		m->x=x;
		m->y=y;
		list<el2>::iterator i = v[x].end();
		i--;
		m->xi=i;
		i=v[y].end();
		i--;
		m->yi=i;
		v[x].back().m=m;
		v[y].back().m=m;
	}
	el tmp;
	tmp.e=0;
	tmp.t=-1;
	tmp.it=v[0].begin();
	bif[0]=true;
	q.push_back(tmp);
	qq.push_back(0);
	while (!q.empty())
	{
		el & tmp = q.back();
		while ((tmp.it!=v[tmp.e].end())&&(((*tmp.it).v==tmp.t)||((*tmp.it).v==-1)))
			tmp.it++;
		if (tmp.it==v[tmp.e].end())
		{
			if (tmp.t!=-1)
			{
				if (qq.back()==tmp.e)
				{
					list<int> l;
					l.push_back(tmp.e);
					l.push_back(tmp.t);
					res.push_back(l);
					qq.pop_back();
				}
			}
			q.pop_back();
		} else {
			int i = (*tmp.it).v;
			muchie * m = (*tmp.it).m;
			tmp.it++;
			if (bif[i])
			{
				(*m->xi).v=-1;
				(*m->yi).v=-1;
				list<int> l;
				l.push_back(i);
				while (qq.back()!=i)
				{
					l.push_back(qq.back());
					qq.pop_back();
				}
				res.push_back(l);
			} else {
				bif[i]=true;
				el tmp_;
				tmp_.e=i;
				tmp_.t=tmp.e;
				tmp_.it=v[i].begin();
				q.push_back(tmp_);
				qq.push_back(i);
			}
		}
	}
	fprintf(fout, "%d\n",(int)res.size());
	for (list<list<int> >::iterator i = res.begin(); i!=res.end(); i++)
	{
		for (list<int>::iterator j=(*i).begin(); j!=(*i).end(); j++)
			fprintf(fout, "%d ",(*j)+1);
		fputc('\n', fout);
	}
	fclose(fin);
	fclose(fout);
    return 0;
}