Cod sursa(job #2966700)

Utilizator DordeDorde Matei Dorde Data 18 ianuarie 2023 10:46:56
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#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;
}