Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "iostream"
- #include "stack"
- using namespace std;
- int main() {
- int n, a, b, v, parent, maximum = 0;
- stack<int> S;
- cin >> n;
- int parents[n], d[n][n];
- // Nas graf jest definiowany jako macierz sąsiedztw
- bool graf[n][n], visited[n];
- // Zerowanie macierzy sąsiedztw, tablicy odwiedzin, tablicy odległości i tablicy rodziców
- for (int i = 0; i<n; i++) {
- visited[i] = false;
- parents[n] = -1;
- for (int j = 0; j<n; j++) {
- graf[i][j] = false;
- d[i][j] = 0;
- }
- }
- // Wczytywanie grafu
- for (int i = 0; i<n-1; i++) {
- cin >> a >> b;
- graf[a-1][b-1] = true;
- graf[b-1][a-1] = true;
- }
- // DFS realizowany iteracyjnie
- S.push(0);
- while (!S.empty()) {
- v = S.top();
- S.pop();
- parent = parents[v];
- // Wypełnianie tablicy odległości
- if (parent != -1) {
- for (int i = 0; i<n; i++) {
- if (!visited[i]) continue;
- d[v][i] = d[parent][i] + 1;
- d[i][v] = d[i][parent] + 1;
- if (d[i][v]>maximum) maximum = d[i][v];
- }
- }
- // Przechodzenie wgłąb kolejnych wierzchołków
- visited[v] = true;
- for (int i = 0; i<n; i++) {
- if (!graf[v][i]) continue;
- if (!visited[i]) {
- S.push(i);
- parents[i] = v;
- }
- }
- }
- cout << maximum << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement