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.     // Build adjacency list
  12.     vector<vector<int>> adj(n+1);
  13.     for(int i = 0; i < m; i++){
  14.         int u, v;
  15.         cin >> u >> v;
  16.         adj[u].push_back(v);
  17.         adj[v].push_back(u);
  18.     }
  19.  
  20.     // Iterative DFS to produce the Euler‐tour of the spanning tree
  21.     vector<bool> seen(n+1,false);
  22.     vector<int> euler;
  23.     euler.reserve(2*n);
  24.  
  25.     // stack entries: (node, next child index)
  26.     vector<pair<int,int>> st;
  27.     st.reserve(n);
  28.     st.emplace_back(1, 0);
  29.     seen[1] = true;
  30.  
  31.     while(!st.empty()){
  32.         auto &top = st.back();
  33.         int u = top.first;
  34.         int &ci = top.second;
  35.         if(ci == 0){
  36.             // first time visiting u
  37.             euler.push_back(u);
  38.         }
  39.         if(ci < (int)adj[u].size()){
  40.             int v = adj[u][ci++];
  41.             if(!seen[v]){
  42.                 seen[v] = true;
  43.                 st.emplace_back(v, 0);
  44.             }
  45.         } else {
  46.             // finished all children of u
  47.             euler.push_back(u);
  48.             st.pop_back();
  49.         }
  50.     }
  51.  
  52.     // We have at most 2n-1 entries
  53.     int S = (int)euler.size();
  54.     // ceil( S / k )
  55.     int limit = (S + k - 1) / k;
  56.  
  57.     // Now print exactly k routes
  58.     int p = 0;
  59.     for(int i = 0; i < k; i++){
  60.         if(p < S){
  61.             int sz = min(limit, S - p);
  62.             cout << sz;
  63.             for(int j = 0; j < sz; j++, p++){
  64.                 cout << ' ' << euler[p];
  65.             }
  66.             cout << "\n";
  67.         } else {
  68.             // No more real entries: trivial route at node 1
  69.             cout << "1 1\n";
  70.         }
  71.     }
  72.  
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
5 4 2
1 2
1 3
1 4
1 5
stdout
copy 
5 1 2 2 3 3
5 4 4 5 5 1
https://ideone.com/zsXBW5
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!