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,int> bfs_far(int start, vector<int>& comp) {
  9.     vector<int> dist(n+1, -1);
  10.     queue<int> q;
  11.     dist[start] = 0;
  12.     q.push(start);
  13.     int far = start;
  14.     while(!q.empty()) {
  15.         int u = q.front(); q.pop();
  16.         for(int v : g[u]) {
  17.             if(dist[v] == -1) {
  18.                 dist[v] = dist[u] + 1;
  19.                 q.push(v);
  20.                 if(dist[v] > dist[far]) far = v;
  21.             }
  22.         }
  23.     }
  24.     return {far, dist[far]};
  25. }
  26.  
  27. vector<int> bfs_path(int s, int t) {
  28.     vector<int> dist(n+1, -1), par(n+1, -1);
  29.     queue<int> q;
  30.     dist[s] = 0;
  31.     q.push(s);
  32.     while(!q.empty()) {
  33.         int u = q.front(); q.pop();
  34.         for(int v : g[u]) if(dist[v] == -1) {
  35.             dist[v] = dist[u] + 1;
  36.             par[v] = u;
  37.             q.push(v);
  38.         }
  39.     }
  40.     vector<int> path;
  41.     if(dist[t] == -1) return path;
  42.     for(int cur=t; cur!=-1; cur=par[cur]) path.push_back(cur);
  43.     reverse(path.begin(), path.end());
  44.     return path;
  45. }
  46.  
  47. void dfs_heuristic(int u, vector<int>& path, vector<bool>& used) {
  48.     if(path.size() > bestPath.size()) bestPath = path;
  49.     for(int v : g[u]) {
  50.         if(!used[v]) {
  51.             used[v] = true;
  52.             path.push_back(v);
  53.             dfs_heuristic(v, path, used);
  54.             path.pop_back();
  55.             used[v] = false;
  56.         }
  57.     }
  58. }
  59.  
  60. void solve_component(vector<int>& comp) {
  61.     if(comp.empty()) return;
  62.     int start = comp[0];
  63.     auto [a, _] = bfs_far(start, comp);
  64.     auto [b, __] = bfs_far(a, comp);
  65.     vector<int> path = bfs_path(a,b);
  66.     if(path.size() > bestPath.size()) bestPath = path;
  67.  
  68.     // thử DFS từ 2 đầu
  69.     for(int root : {a, b}) {
  70.         vector<int> cur = {root};
  71.         vector<bool> used(n+1,false);
  72.         used[root] = true;
  73.         dfs_heuristic(root, cur, used);
  74.     }
  75. }
  76.  
  77. int main() {
  78.     ios::sync_with_stdio(false);
  79.     cin.tie(nullptr);
  80.  
  81.     cin >> n >> m;
  82.     g.assign(n+1, {});
  83.     for(int i=0;i<m;i++) {
  84.         int u,v; cin >> u >> v;
  85.         g[u].push_back(v);
  86.         g[v].push_back(u);
  87.     }
  88.  
  89.     vector<bool> vis(n+1,false);
  90.     for(int i=1;i<=n;i++) if(!vis[i]) {
  91.         vector<int> comp;
  92.         queue<int> q;
  93.         q.push(i);
  94.         vis[i] = true;
  95.         while(!q.empty()) {
  96.             int u = q.front(); q.pop();
  97.             comp.push_back(u);
  98.             for(int v : g[u]) if(!vis[v]) {
  99.                 vis[v] = true;
  100.                 q.push(v);
  101.             }
  102.         }
  103.         solve_component(comp);
  104.     }
  105.  
  106.     cout << (int)bestPath.size()-1 << "\n";
  107.     for(int x : bestPath) cout << x << " ";
  108.     cout << "\n";
  109. }
  110.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
6 5
1 2
2 3
3 4
2 5
5 6
stdout
copy 
4
4 3 2 5 6
https://ideone.com/tzltDL
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!