Pagini recente » Cod sursa (job #2365226) | Cod sursa (job #1331536) | Cod sursa (job #1129198) | Cod sursa (job #3164198) | Cod sursa (job #2285710)
#include <bits/stdc++.h>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct Elem
{
int val;
Elem *next;
};
struct Item
{
Elem *st,*cur;
};
struct Mem
{
int ax,bx;
Mem *bak;
};
vector <Item> Grupe;
int n,m,a,b,nrgrupe,nrramuri;
int i,cand;
Elem *leg,*parc2;
Item Adiac[100005];
int low[100005];
int dfn[100005];
Mem *sf,*ad,*sters;
Item hol;
void dfs(int,int);
void extractcomp(int,int);
int main()
{
fin>>n>>m;
hol.st=0;
hol.cur=0;
Grupe.push_back(hol);
for (i=1;i<=n;i++)
{
Adiac[i].st=new Elem;
Adiac[i].st->val=0;
Adiac[i].st->next=0;
Adiac[i].cur=Adiac[i].st;
}
sf=new Mem;
sf->bak=0;
while (m)
{
m--;
fin>>a>>b;
leg=new Elem;
leg->val=b;
leg->next=0;
Adiac[a].cur->next=leg;
Adiac[a].cur=leg;
leg=new Elem;
leg->val=a;
leg->next=0;
Adiac[b].cur->next=leg;
Adiac[b].cur=leg;
}
dfs(1,0);
fout<<nrgrupe<<"\n";
for (i=1;i<=nrgrupe;i++)
{
parc2=Grupe.at(i).st->next;
while (parc2!=0)
{
fout<<parc2->val<<" ";
parc2=parc2->next;
}
fout<<"\n";
}
return 0;
}
void dfs(int x,int tx)
{
Elem *i2;
int y;
cand++;
dfn[x]=low[x]=cand;
i2=Adiac[x].st->next;
while (i2!=NULL)
{
y=i2->val;
if (dfn[y]==0)
{
if (x==1)
nrramuri++;
ad=new Mem;
ad->bak=sf;
ad->ax=y;
ad->bx=x;
sf=ad;
dfs(y,x);
low[x]=min(low[y],low[x]);
if (low[y]>=dfn[x])
extractcomp(y,x);
}
else
{
if (y!=tx&&dfn[y]<dfn[x])
{
ad=new Mem;
ad->bak=sf;
ad->ax=y;
ad->bx=x;
sf=ad;
low[x]=min(low[x],low[y]);
}
}
i2=i2->next;
}
}
void extractcomp(int x,int tx)
{
bool Select[100005];
int i2,a2,b2;
Item holder;
for (i2=1;i2<=100000;i2++)
Select[i2]=0;
nrgrupe++;
holder.st=new Elem;
holder.st->next=0;
holder.st->val=0;
holder.cur=holder.st;
Grupe.push_back(holder);
Mem *parc;
parc=sf;
do
{
sters=parc;
a2=parc->ax;
b2=parc->bx;
if (Select[a2]==0)
{
Select[a2]=1;
leg=new Elem;
leg->val=a2;
leg->next=0;
Grupe.at(nrgrupe).cur->next=leg;
Grupe.at(nrgrupe).cur=leg;
}
if (Select[b2]==0)
{
Select[b2]=1;
leg=new Elem;
leg->val=b2;
leg->next=0;
Grupe.at(nrgrupe).cur->next=leg;
Grupe.at(nrgrupe).cur=leg;
}
sf=parc->bak;
parc=parc->bak;
delete sters;
} while (a2!=x||b2!=tx);
}