Pagini recente » Cod sursa (job #809810) | Cod sursa (job #3141177) | Cod sursa (job #2966700)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("johnie.in");
ofstream fout("johnie.out");
int const N = 5e5 + 3;
int n , m , a , b;
int viz[N] , from[N] , to[N] , gata[N];
stack<int> st;
pair<int , int> e[N];
vector<int> v[N];
int main(){
fin >> n >> m;
for(int i = 1 ; i <= m ; ++ i){
fin >> from[i] >> to[i];
v[from[i]].push_back(i);
v[to[i]].push_back(i);
}
for(int i = 1 ; i <= n ; ++ i){
if(v[i].size() % 2 == 1){
v[0].push_back(++ m);
from[m] = 0 , to[m] = i;
}
}
vector<vector<int> > ans;
for(int i = 1 ; i <= n ; ++ i){
if(gata[i])continue;
st.push(i);
vector<int> ciclu;
while(!st.empty()){
int x = st.top();
if(v[x].empty()){
ciclu.push_back(x);
gata[x] = 1;
st.pop();
}else{
int edge = v[x].back();
int y = from[edge] ^ to[edge] ^ x;
v[x].pop_back();
if(viz[edge])
continue;
viz[edge] = 1;
st.push(y);
}
}
ans.push_back(ciclu);
}
fout << ans.size() << '\n';
for(auto &V : ans){
fout << V.size() << ' ';
auto sep = "";
for(int y : V){
if(y)fout << sep << y , sep = " ";
}
fout << '\n';
}
return 0;
}