Pagini recente » Cod sursa (job #2961171) | Cod sursa (job #21967) | Cod sursa (job #109956) | Cod sursa (job #2817058) | Cod sursa (job #553890)
Cod sursa(job #553890)
#include <cstdio>
#include <list>
using namespace std;
int n,m,v[100003],nr1=0,nivMin[100003],punctDeInflexiune[100003],nr=1,t[100003];
list<int> l[100003];
list<int> l2[100003];
void citire(){
scanf("%d %d",&n,&m);
int i,x,y;
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y);
l[x].push_back(y);
l[y].push_back(x);
}
}
void df(int nod){
v[nod]=1;
list<int>::iterator it;
nivMin[nod]=nod;
for(it=l[nod].begin();it!=l[nod].end();++it){
if(v[*it]==0){
df(*it);
t[*it]=nod;
if(nod!=1){
if(nivMin[nod]>nivMin[*it])
nivMin[nod]=nivMin[*it];
if(nivMin[*it]>=nod && punctDeInflexiune[nod]==0){
punctDeInflexiune[nod]=1;
}
}
}
else {
if(nivMin[nod]>*it)
nivMin[nod]=*it;
}
}
}
void df2(int nod){
v[nod]=1;
list<int>::iterator it;
for(it=l[nod].begin();it!=l[nod].end();++it)
if(v[*it]==0){
df2(*it);
}
if(!(punctDeInflexiune[1]==1 && nod==1))
l2[nr].push_back(nod);
if(punctDeInflexiune[t[nod]]==1){
l2[nr].push_back(t[nod]);
nr++;
}
}
void initV(){
int i;
for(i=1;i<=n;i++)
v[i]=0;
}
void afisare(){
int i;
printf("%d\n",nr);
list<int>::iterator it;
for(i=1;i<=nr;i++){
for(it=l2[i].begin();it!=l2[i].end();++it){
printf("%d ",*it);
}
printf("\n");
}
}
void rezolvare(){
df(1);
list<int>::iterator it;
for(it=l[1].begin();it!=l[1].end();++it)
nr1++;
if(nr1>1){
punctDeInflexiune[1]=1;
}
initV();
df2(1);
}
int main(){
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
rezolvare();
afisare();
return 0;
}