Advertisement
MrFishPL

Zadanie z grafem - C++

Nov 27th, 2021
887
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include "iostream"
  2. #include "stack"
  3.  
  4. using namespace std;
  5. int main() {
  6.   int n, a, b, v, parent, maximum = 0;
  7.   stack<int> S;
  8.  
  9.   cin >> n;
  10.  
  11.   int parents[n], d[n][n];
  12.  
  13.   // Nas graf jest definiowany jako macierz sąsiedztw
  14.   bool graf[n][n], visited[n];
  15.  
  16.   // Zerowanie macierzy sąsiedztw, tablicy odwiedzin, tablicy odległości i tablicy rodziców
  17.   for (int i = 0; i<n; i++) {
  18.     visited[i] = false;
  19.     parents[n] = -1;
  20.     for (int j = 0; j<n; j++) {
  21.       graf[i][j] = false;
  22.       d[i][j] = 0;
  23.     }
  24.   }
  25.  
  26.   // Wczytywanie grafu
  27.   for (int i = 0; i<n-1; i++) {
  28.     cin >> a >> b;
  29.  
  30.     graf[a-1][b-1] = true;
  31.     graf[b-1][a-1] = true;
  32.   }
  33.  
  34.   // DFS realizowany iteracyjnie
  35.   S.push(0);
  36.   while (!S.empty()) {
  37.     v = S.top();
  38.     S.pop();
  39.     parent = parents[v];
  40.  
  41.     // Wypełnianie tablicy odległości
  42.     if (parent != -1) {
  43.       for (int i = 0; i<n; i++) {
  44.         if (!visited[i]) continue;
  45.         d[v][i] = d[parent][i] + 1;
  46.         d[i][v] = d[i][parent] + 1;
  47.  
  48.         if (d[i][v]>maximum) maximum = d[i][v];
  49.       }
  50.     }
  51.  
  52.     // Przechodzenie wgłąb kolejnych wierzchołków
  53.     visited[v] = true;
  54.     for (int i = 0; i<n; i++) {
  55.       if (!graf[v][i]) continue;
  56.       if (!visited[i]) {
  57.         S.push(i);
  58.         parents[i] = v;
  59.       }
  60.     }
  61.   }
  62.  
  63.   cout << maximum << endl;
  64.  
  65.   return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement