Pagini recente » Cod sursa (job #2415888) | Cod sursa (job #2943769) | Cod sursa (job #818464) | Cod sursa (job #2927355) | Cod sursa (job #1223710)
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<vector>
#include<stack>
using namespace std;
const int maxn = 50004;
const int maxm = 100005;
vector <int> a[maxn];
vector <int> sol[maxm];
stack <int> st;
int nr_grad_impar,nr_conexe_cicluri,etape;
int i,j,n,m,x,y,nr;
bool este,viz[maxn];
void dfs(int nod){
if(a[nod].size()&1) este=0;
viz[nod]=1;
for(int j=0;j<(int)a[nod].size();j++)
if(!viz[a[nod][j]]) dfs(a[nod][j]);
}
void euler(const int x){
st.push(x);
while(!st.empty())
{
int nod=st.top();
if(a[nod].size()){
int vecin=a[nod].back();
a[nod].pop_back();
int j=a[vecin].size()-1;
while(j>=0 && a[vecin][j]!=nod) j--;
a[vecin][j]=a[vecin].back();
a[vecin].pop_back();
st.push(vecin);
}
else{//nu mai am vecini
st.pop();
if(nod) sol[nr].push_back(nod);//nu adaug nodul 0
else nr++;
}
}
}
int main(void){
assert(freopen("johnie.in","r",stdin));
assert(freopen("johnie.out","w",stdout));
assert(scanf("%d %d",&n,&m)==2);
for(i=1;i<=m;i++){
assert(scanf("%d %d",&x,&y)==2);
a[x].push_back(y);
a[y].push_back(x);
}
for(i=1;i<=n;i++) viz[i]=0;
for(i=1;i<=n;i++)
if(!viz[i] && a[i].size()){
este=1;
dfs(i);
nr_conexe_cicluri+=este;
}
for(i=1;i<=n;i++)
if(a[i].size()&1){//unesc nodul 0 cu nodurile cu grad impar
nr_grad_impar++;
a[0].push_back(i);
a[i].push_back(0);
}
etape = nr_conexe_cicluri + nr_grad_impar/2;
printf("%d\n",etape);
nr=0;
euler(0);
if(nr_conexe_cicluri){//adaug si componentele conexe care sunt cicluri (daca exista)
for(i=1;i<=n;i++)
if(a[i].size()) euler(i);
}
for(i=1;i<=etape;i++)
{
printf("%d ",sol[i].size());
for(j=0;j<(int)sol[i].size();j++) printf("%d ",sol[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}