fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using pii = pair<int,int>;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int T;
  10.     cin >> T;
  11.     while (T--) {
  12.         int n, m;
  13.         cin >> n >> m;
  14.         vector<vector<int>> adj(n+1);
  15.         for (int i = 0; i < m; i++) {
  16.             int u, v;
  17.             cin >> u >> v;
  18.             adj[u].push_back(v);
  19.             adj[v].push_back(u);
  20.         }
  21.  
  22.         // 1) Build a DFS‐tree (iterative) to record parent & depth
  23.         vector<int> parent(n+1, 0), depth(n+1, 0);
  24.         vector<bool> vis(n+1, false);
  25.         int maxd = 0, maxdNode = 1;
  26.  
  27.         // stack for (node, next_child_index)
  28.         vector<pair<int,int>> st;
  29.         st.reserve(n);
  30.         st.emplace_back(1, 0);
  31.         vis[1] = true;
  32.         parent[1] = 0;
  33.         depth[1] = 1;
  34.         maxd = 1;
  35.  
  36.         while (!st.empty()) {
  37.             auto &top = st.back();
  38.             int u = top.first;
  39.             int &ci = top.second;
  40.             if (ci < (int)adj[u].size()) {
  41.                 int v = adj[u][ci++];
  42.                 if (!vis[v]) {
  43.                     vis[v] = true;
  44.                     parent[v] = u;
  45.                     depth[v] = depth[u] + 1;
  46.                     if (depth[v] > maxd) {
  47.                         maxd = depth[v];
  48.                         maxdNode = v;
  49.                     }
  50.                     st.emplace_back(v, 0);
  51.                 }
  52.                 // else already visited: skip
  53.             } else {
  54.                 st.pop_back();
  55.             }
  56.         }
  57.  
  58.         int need = (n + 1) / 2;  // ceil(n/2)
  59.  
  60.         // 2) If we found a node at depth >= need, output that root→node path
  61.         if (maxd >= need) {
  62.             cout << "PATH\n" << maxd << "\n";
  63.             vector<int> path;
  64.             int cur = maxdNode;
  65.             while (cur != 0) {
  66.                 path.push_back(cur);
  67.                 cur = parent[cur];
  68.             }
  69.             reverse(path.begin(), path.end());
  70.             for (int x : path) {
  71.                 cout << x << " ";
  72.             }
  73.             cout << "\n";
  74.             continue;
  75.         }
  76.  
  77.         // 3) Otherwise, group nodes by depth and pair within each depth
  78.         vector<vector<int>> byDepth(maxd+1);
  79.         for (int u = 1; u <= n; u++) {
  80.             byDepth[depth[u]].push_back(u);
  81.         }
  82.         vector<pii> pairs;
  83.         pairs.reserve(need);
  84.  
  85.         for (int d = 1; d <= maxd; d++) {
  86.             auto &bucket = byDepth[d];
  87.             // pair off in index‐order
  88.             for (int i = 0; i + 1 < (int)bucket.size(); i += 2) {
  89.                 pairs.emplace_back(bucket[i], bucket[i+1]);
  90.             }
  91.         }
  92.  
  93.         // by the argument, we paired at least need nodes ⇒ pairs.size()*2 >= need
  94.         cout << "PAIRING\n" << pairs.size() << "\n";
  95.         for (auto &pr : pairs) {
  96.             cout << pr.first << " " << pr.second << "\n";
  97.         }
  98.     }
  99.  
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
6 5
1 4
2 5
3 6
1 5
3 5
6 5
1 4
2 5
3 6
1 5
3 5
12 14
1 2
2 3
3 4
4 1
1 5
1 12
2 6
2 7
3 8
3 9
4 10
4 11
2 4
1 3
12 14
1 2
2 3
3 4
4 1
1 5
1 12
2 6
2 7
3 8
3 9
4 10
4 11
2 4
1 3
stdout
copy 
PATH
4
1 5 3 6 
PATH
4
1 5 3 6 
PAIRING
4
2 5
3 6
4 8
10 11
PAIRING
4
2 5
3 6
4 8
10 11
https://ideone.com/jIRYN4
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!