fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int M = 1e9 + 7;
  5.  
  6.  
  7. // 27th Aug Adobe tree OA
  8.  
  9. unordered_set<int> st;
  10. pair<int, int> bfs(int node, vector<int> adj[], int n)
  11. {
  12.     queue<int> q;
  13.     q.push(node);
  14.     vector<int> dis_from(n + 1, -1);
  15.     dis_from[node] = 0;
  16.     int ma = 0;
  17.     int farthest_node = node;
  18.     while (!q.empty())
  19.     {
  20.         int nd = q.front();
  21.         q.pop();
  22.         if (dis_from[nd] > ma)
  23.         {
  24.             farthest_node = nd;
  25.             ma = dis_from[nd];
  26.         }
  27.         for (auto it : adj[nd])
  28.         {
  29.             if (dis_from[it] == -1)
  30.             {
  31.                 q.push(it);
  32.                 dis_from[it] = dis_from[nd] + 1;
  33.             }
  34.         }
  35.     }
  36.     for (int i = 1; i <= n; i++)
  37.     {
  38.         if (dis_from[i] == ma)
  39.             st.insert(i);
  40.     }
  41.     return {farthest_node, ma};
  42. }
  43.  
  44. int main()
  45. {
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.     int n, e;
  49.     cin >> n >> e;
  50.     vector<int> adj[n + 1];
  51.     for (int i = 0; i < e; i++)
  52.     {
  53.         int x, y;
  54.         cin >> x >> y;
  55.         adj[x].push_back(y);
  56.         adj[y].push_back(x);
  57.     }
  58.     pair<int, int> firstbfs = bfs(1, adj, n);
  59.     int u = firstbfs.first;
  60.  
  61.     pair<int, int> secondbfs = bfs(u, adj, n);
  62.     for (auto it : st)
  63.         cout << it << " ";
  64.  
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
7 6
1 2
2 3
3 4
3 5
1 6
1 7
stdout
copy 
7 6 4 5
https://ideone.com/DOd9Qf
language:
C++14 (gcc 8.3)
created:
1 day 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!