Question

Policz rozmiary poddrzew wszystkich poddrzew drzewa. Drzewo ukorzenienie jest w wierzchołku nr. 1. Poddrzewa w liściach maja rozmiar 1.

W pierwszym wierszu wejścia znajduje się N oznaczająca rozmiar drzewa. W kolejnych N-1 wierszach znajdują się pary, a[i], b[i] oznaczające krawędzie między wierzchołkami a i b.

Na wyjściu powinno znaleść się N wierszy. W każdym wierszu powinna znaleść się para {i, S[i]} oznaczająca odpowiednio numer i-tego wierzchołka i rozmiar jego podrzewa

Answer 1

Verified answer

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> adj;

vector<int> subtreeSizes;

void dfs(int node) {

   subtreeSizes[node] = 1; // Rozmiar poddrzewa dla liścia wynosi 1

   cout << "Odwiedzam wierzcholek: " << node << endl;

   for (int child : adj[node]) {

       dfs(child);

       subtreeSizes[node] += subtreeSizes[child]; // Sumowanie rozmiarów poddrzew

   }

   cout << "Rozmiar poddrzewa dla wierzcholka " << node << " wynosi: " << subtreeSizes[node] << endl;

}

int main() {

   int N;

   cout << "Podaj rozmiar drzewa: ";

   cin >> N;

   adj.resize(N + 1); // Tworzenie wektora sąsiedztwa

   subtreeSizes.resize(N + 1); // Tworzenie wektora rozmiarów poddrzew

   cout << "Podaj " << N - 1 << " krawedzi:" << endl;

   // Wczytywanie krawędzi

   for (int i = 0; i < N - 1; i++) {

       int a, b;

       cin >> a >> b;

       adj[a].push_back(b);

   }

   dfs(1); // Wywołanie funkcji dfs dla korzenia (wierzchołka nr 1)

   cout << "Rozmiary poddrzew:" << endl;

   // Wypisywanie numerów wierzchołków i rozmiarów poddrzew

   for (int i = 1; i <= N; i++) {

       cout << "Wierzcholek " << i << ": " << subtreeSizes[i] << endl;

   }

   return 0;

}