Vserosbuybuy

Untitled

Jun 15th, 2020
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include<iostream>
  2. #include<queue>
  3. #include <vector>
  4. using namespace std;
  5. int way[2500][2500];
  6. int used[110000];
  7. int matr[2500][2500];
  8. int maxs[10000];
  9. int t = 0;
  10. void dfs(int v, int n) {
  11.     used[v] = 1;
  12.     int maxx = 0;
  13.     int max1 = 0;
  14.     for (int i = 0; i < n; ++i) {
  15.         if (!used[i] && matr[v][i]) {
  16.             dfs(i, n);
  17.             int pr_max = 0;
  18.             for (int j = 0; j < n; ++j) {
  19.                 pr_max = max(pr_max, way[i][j]);
  20.             }
  21.             way[v][i] = pr_max + 1;
  22.         }
  23.     }
  24.     for (int j = 0; j < n; ++j) {
  25.         if (way[v][j] > maxx) {
  26.             max1 = maxx; maxx = way[v][j];
  27.         }
  28.         else {
  29.             if (way[v][j] > max1)
  30.                 max1 = way[v][j];
  31.         }
  32.     }
  33.     int s_max = maxx + max1;
  34.     maxs[t] = s_max;
  35.     t++;
  36. }
  37. int main() {
  38. #ifdef SYSTEM
  39.     freopen("In.txt", "r", stdin);
  40.     freopen("Out.txt", "w", stdout);
  41. #endif
  42.     int n;
  43.     cin >> n;
  44.     for (int i = 0; i < n - 1; ++i) {
  45.         int a, b;
  46.         cin >> a >> b;
  47.         --a;
  48.         --b;
  49.         matr[a][b] = 1;
  50.         matr[b][a] = 1;
  51.     }
  52.     for (int j = 0; j < n; ++j) {
  53.         if (!used[j]) {
  54.             dfs(j, n);
  55.         }
  56.     }
  57.     int sup_max = 0;
  58.     for (int k = 0; k < n; ++k) {
  59.         if (maxs[k] > sup_max) sup_max = maxs[k];
  60.     }
  61.     cout << sup_max + 1;
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment