Advertisement
shtirmann

Untitled

Feb 21st, 2023
691
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define close_all { \
  4. out.close();      \
  5. in.close(); }
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10.  
  11. int n;
  12. map<int, vector<int>> graph;
  13. set<int> curr;
  14. bool chk;
  15.  
  16. vector<int> bfs(int start) {
  17.   deque<int> q;
  18.   q.push_back(start);
  19.   map<int, bool> used;
  20.   vector<int> d(n);
  21.   used[start] = true;
  22.   while (!q.empty()) {
  23.     int v = q.front();
  24.     q.pop_front();
  25.     for (int i = 0; i < graph[v].size(); ++i) {
  26.       int to = graph[v][i];
  27.       if (!used[to]) {
  28.         used[to] = true;
  29.         q.push_back(to);
  30.         d[to] = d[v] + 1;
  31.       }
  32.     }
  33.   }
  34.   return d;
  35. }
  36.  
  37. int diameter() {
  38.   int v, u, w;
  39.   v = u = w = 0;
  40.   vector<int> d = bfs(v);
  41.   for (int i = 0; i < n; ++i) {
  42.     if (d[i] > d[u]) {
  43.       u = i;
  44.     }
  45.   }
  46.   d = bfs(u);
  47.   for (int i = 0; i < n; ++i) {
  48.     if (d[i] > d[w]) {
  49.       w = i;
  50.     }
  51.   }
  52.   return d[w];
  53. }
  54.  
  55. signed main() {
  56.   int m;
  57.   cin >> n >> m;
  58.  
  59.   for (int i = 0; i < m; ++i) {
  60.     int a, b;
  61.     cin >> a >> b;
  62.     graph[a - 1].push_back(b - 1);
  63.     graph[b - 1].push_back(a - 1);
  64.   }
  65.  
  66.   cout << diameter();
  67.   return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement