fork(1) 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.  
  8. pair<int, vector<int>> bfs_path(int s) {
  9.     vector<int> dist(n+1, -1), par(n+1, -1);
  10.     queue<int> q;
  11.     dist[s] = 0;
  12.     q.push(s);
  13.     int far = s;
  14.     while(!q.empty()) {
  15.         int u = q.front(); q.pop();
  16.         for(int v : g[u]) if(dist[v] == -1) {
  17.             dist[v] = dist[u] + 1;
  18.             par[v] = u;
  19.             q.push(v);
  20.             if(dist[v] > dist[far]) far = v;
  21.         }
  22.     }
  23.     return {far, par};
  24. }
  25.  
  26. vector<int> build_path(int s, int t, vector<int>& par) {
  27.     vector<int> path;
  28.     for(int cur = t; cur != -1; cur = par[cur]) path.push_back(cur);
  29.     reverse(path.begin(), path.end());
  30.     return path;
  31. }
  32.  
  33. int main() {
  34.     ios::sync_with_stdio(false);
  35.     cin.tie(nullptr);
  36.  
  37.     cin >> n >> m;
  38.     g.assign(n+1, {});
  39.     for(int i=0;i<m;i++) {
  40.         int u,v; cin >> u >> v;
  41.         g[u].push_back(v);
  42.         g[v].push_back(u);
  43.     }
  44.  
  45.     vector<bool> vis(n+1,false);
  46.     for(int i=1;i<=n;i++) if(!vis[i]) {
  47.         vector<int> comp;
  48.         queue<int> q;
  49.         q.push(i);
  50.         vis[i] = true;
  51.         while(!q.empty()) {
  52.             int u = q.front(); q.pop();
  53.             comp.push_back(u);
  54.             for(int v : g[u]) if(!vis[v]) {
  55.                 vis[v] = true;
  56.                 q.push(v);
  57.             }
  58.         }
  59.  
  60.         int start = comp[0];
  61.         auto [a, _] = bfs_path(start);
  62.         auto [b, par] = bfs_path(a);
  63.         vector<int> path = build_path(a, b, par);
  64.  
  65.         if(path.size() > bestPath.size()) bestPath = path;
  66.     }
  67.  
  68.     cout << bestPath.size() << "\n";
  69.     for(int x : bestPath) cout << x << " ";
  70.     cout << "\n";
  71. }
  72.  
Success #stdin #stdout 0s 5308KB
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/AhDJKx
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!