Pagini recente » Cod sursa (job #1040646) | Cod sursa (job #2058162) | Cod sursa (job #758441) | Cod sursa (job #1882102) | Cod sursa (job #2100141)
#include <iostream>
#include <fstream>
#define nmax 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,viz[nmax+5],sol[nmax/2],solu[nmax+5],t=0,u=0;
struct nod
{
int info;
nod *urm, *ante;
}*v[nmax+5],*c,*d,*ctc,*e,*w[nmax+5];
void adauga(int k)
{
if(!ctc->urm)
{
d=new nod;
d->urm=0;
d->info=k;
d->ante=ctc;
ctc->urm=d;
e=d;
}
else
{
d=new nod;
d->urm=0;
d->ante=e;
d->info=k;
e->urm=d;
e=d;
}
}
void dfs(int k,int caz)
{
if(caz==1)
{
nod *gg;
viz[k]=1;
gg=v[k];
while(gg->urm)
{
gg=gg->urm;
if(!viz[gg->info])
dfs(gg->info,caz);
}
adauga(k);
}
else
{
nod *gg;
viz[k]=0;
gg=w[k];
while(gg->urm)
{
gg=gg->urm;
if(viz[gg->info])
dfs(gg->info,caz);
}
solu[++u]=k;
sol[t]++;
}
}
void tc(int caz)
{
if(caz==1)
for(int i=1;i<=n;i++)
if(!viz[i])
dfs(i,caz);
if(caz==2)
{
c=e;
while(c->ante)
{
if(viz[c->info])
{
t++;dfs(c->info,caz);
}
c=c->ante;
}
}
}
int main()
{
int x,y;
fin>>n>>m;
for(int i=1;i<=n;i++)
{
v[i]=new nod;
v[i]->info=i;
v[i]->urm=0;
w[i]=new nod;
w[i]->info=i;
w[i]->urm=0;
}
while(fin>>x>>y)
{
c=v[x];
while(c->urm)
c=c->urm;
d=new nod;
d->urm=0;
d->info=y;
d->ante=c;
c->urm=d;
c=w[y];
while(c->urm)
c=c->urm;
d=new nod;
d->urm=0;
d->info=x;
c->urm=d;
d->ante=c;
}
ctc=new nod;
ctc->urm=0;
ctc->info=0;
ctc->ante=0;
tc(1);
tc(2);
fout<<t<<"\n";
int j=1;
for(int i=1;i<=t;i++)
{
x=j;
while(j<x+sol[i])
{
fout<<solu[j]<<" ";
j++;
}
fout<<"\n";
}
return 0;
}