fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int n, m, k;
  9.     cin >> n >> m >> k;
  10.  
  11.     vector<vector<int>> adj(n+1);
  12.     for(int i = 0; i < m; i++){
  13.         int u,v;
  14.         cin >> u >> v;
  15.         adj[u].push_back(v);
  16.         adj[v].push_back(u);
  17.     }
  18.  
  19.     // 1) Build an Euler-tour that records only real moves
  20.     vector<bool> seen(n+1,false);
  21.     vector<int> euler;
  22.     euler.reserve(2*n);
  23.  
  24.     // stack entries: (node u, parent p, next-child index ci)
  25.     vector<array<int,3>> st;
  26.     st.reserve(n);
  27.     st.push_back({1,0,0});
  28.     seen[1]=true;
  29.     euler.push_back(1);
  30.  
  31.     while(!st.empty()){
  32.         auto &top = st.back();
  33.         int u = top[0], p = top[1], &ci = top[2];
  34.  
  35.         if(ci < (int)adj[u].size()){
  36.             int v = adj[u][ci++];
  37.             if(!seen[v]){
  38.                 // move u -> v
  39.                 seen[v]=true;
  40.                 euler.push_back(v);
  41.                 st.push_back({v,u,0});
  42.             }
  43.         } else {
  44.             // done with u's children, pop back to parent
  45.             st.pop_back();
  46.             if(!st.empty()){
  47.                 int par = st.back()[0];
  48.                 euler.push_back(par);  // actual move v->par
  49.             }
  50.         }
  51.     }
  52.  
  53.     // 2) Slice into exactly k routes of length ≤ ceil(|euler|/k)
  54.     int S = euler.size();                   // ≤ 2n-1
  55.     int limit = (S + k - 1) / k;            // ceil division
  56.  
  57.     int p = 0;
  58.     for(int i = 0; i < k; i++){
  59.         if(p < S){
  60.             int sz = min(limit, S - p);
  61.             cout << sz;
  62.             for(int j = 0; j < sz; j++, p++){
  63.                 cout << ' ' << euler[p];
  64.             }
  65.             cout << "\n";
  66.         } else {
  67.             // no more moves left: just stay at 1
  68.             cout << "1 1\n";
  69.         }
  70.     }
  71.  
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 4 2
1 2
1 3
1 4
1 5
stdout
copy 
5 1 2 1 3 1
4 4 1 5 1
https://ideone.com/MrxlSt
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!