fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m;
  5. vector<vector<int>> g;
  6. vector<int> bestPath;
  7. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  8.  
  9. vector<int> greedy_path(int start) {
  10.     vector<bool> used(n+1,false);
  11.     vector<int> path;
  12.     int u = start;
  13.     used[u] = true;
  14.     path.push_back(u);
  15.  
  16.     while(true) {
  17.         int nxt = -1, score = -1;
  18.         for(int v : g[u]) if(!used[v]) {
  19.             int cnt = 0;
  20.             for(int w : g[v]) if(!used[w]) cnt++;
  21.             if(cnt > score) {
  22.                 score = cnt;
  23.                 nxt = v;
  24.             }
  25.         }
  26.         if(nxt == -1) break;
  27.         used[nxt] = true;
  28.         path.push_back(nxt);
  29.         u = nxt;
  30.     }
  31.     return path;
  32. }
  33.  
  34. pair<int,int> bfs_far(int s) {
  35.     vector<int> dist(n+1, -1);
  36.     queue<int> q;
  37.     dist[s] = 0;
  38.     q.push(s);
  39.     int far = s;
  40.     while(!q.empty()) {
  41.         int u = q.front(); q.pop();
  42.         for(int v : g[u]) if(dist[v] == -1) {
  43.             dist[v] = dist[u] + 1;
  44.             q.push(v);
  45.             if(dist[v] > dist[far]) far = v;
  46.         }
  47.     }
  48.     return {far, dist[far]};
  49. }
  50.  
  51. int main() {
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(nullptr);
  54.  
  55.     cin >> n >> m;
  56.     g.assign(n+1, {});
  57.     for(int i=0;i<m;i++) {
  58.         int u,v; cin >> u >> v;
  59.         g[u].push_back(v);
  60.         g[v].push_back(u);
  61.     }
  62.  
  63.     vector<bool> vis(n+1,false);
  64.     for(int i=1;i<=n;i++) if(!vis[i]) {
  65.         vector<int> comp;
  66.         queue<int> q;
  67.         q.push(i);
  68.         vis[i] = true;
  69.         while(!q.empty()) {
  70.             int u = q.front(); q.pop();
  71.             comp.push_back(u);
  72.             for(int v : g[u]) if(!vis[v]) {
  73.                 vis[v] = true;
  74.                 q.push(v);
  75.             }
  76.         }
  77.  
  78.  
  79.         vector<int> candidates;
  80.         candidates.push_back(comp[0]);
  81.         auto [a,_] = bfs_far(comp[0]);
  82.         auto [b,__] = bfs_far(a);
  83.         candidates.push_back(a);
  84.         candidates.push_back(b);
  85.  
  86.  
  87.         shuffle(comp.begin(), comp.end(), rng);
  88.         for(int j=0;j<min(5,(int)comp.size());j++) candidates.push_back(comp[j]);
  89.  
  90.         for(int start : candidates) {
  91.             auto path = greedy_path(start);
  92.             if(path.size() > bestPath.size()) bestPath = path;
  93.         }
  94.     }
  95.  
  96.     cout << bestPath.size() << "\n";
  97.     for(int x : bestPath) cout << x << " ";
  98.     cout << "\n";
  99. }
  100.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
6 5
1 2
2 3
3 4
2 5
5 6
stdout
copy 
5
4 3 2 5 6
https://ideone.com/9B1RJf
language:
C++14 (clang 8.0)
created:
11 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!