Pagini recente » Cod sursa (job #2309834) | Cod sursa (job #2866752) | Cod sursa (job #2359147) | Cod sursa (job #2786245) | Cod sursa (job #499244)
Cod sursa(job #499244)
#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;
}