Cod sursa(job #2950390)

Utilizator oskar01oskar the boss oskar01 Data 3 decembrie 2022 17:04:02
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

ifstream cin("johnie.in");
ofstream cout("johnie.out");

#define int long long

struct Info {
    int node;
    int edgeId;
};

int n,m;
vector<vector<Info>> graph;
vector<bitset<1>> vis;
vector<int> path;

void read() {
    cin>>n>>m;
    graph.resize(n+1);
    int a,b,cnt=1;
    for(int i=1;i<=m;i++) {
        cin>>a>>b;
        graph[a].push_back({b,cnt});
        graph[b].push_back({a,cnt});
        cnt++;
    }
}

void dfs(int node) {
    path.push_back(node);
    for(auto it:graph[node]) {
        if(vis[it.edgeId]==1) {
            continue;
        }
        vis[it.edgeId]=1;
        dfs(it.node);
    }
}

void solve() {
    int res=0;
    vis.resize(m+1);
    vector<vector<int>> resV;
    for(int i=1;i<=n;i++) {
        if(graph[i].size()%2==1) {
            res++;
            if(vis[i]==0) {
                path.clear();
                dfs(i);
                resV.push_back(path);
            }
        }
    }
    res/=2;
    cout<<res<<"\n";
    for(auto it1:resV) {
        cout<<it1.size()<<" ";
        for(auto it2:it1) {
            cout<<it2<<" ";
        }
        cout<<"\n";
    }
}

signed main() {
 
    read();
    solve();
    return 0;
}