Mərkəzi tapın (Həll təhlili)

$n$ təpədən ibarət olan bir ağac mövcuddur.

Ağacın centroidu elə bir təpədir ki, onu sildikdə ağac elə bir birləşmiş komponentlərə bölünür ki, hər bir komponentdə olan təpələrin sayı $n /2$ -dən çox deyil.

Məsələdə bütün ağacın centroidlarını tapmaq lazımdır.

Ağacların nümunələrini və onların centroidlarını (yaşıl rəngdə göstərilən) nəzərdən keçirək.

Dərinlik üzrə axtarış $df s (v)$ başladırıq, hansı ki, $s u b [v]$ -də $v$ təpəsindən olan alt ağacdakı təpələrin sayını hesablayır. Verilən nümunələrdə hər təpə $v$ ilə $s u b [v]$ -nin müvafiq dəyərini göstərəcəyik (dərinlik üzrə axtarış bütün nümunələrdə 1-ci təpədən başlayır).

Əgər $v$ təpəsinin övladları $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k-dırsa, onda

s u b_{v} = 1 + s u b_{t o_{1}} + s u b_{t o_{2}} + ... + s u b_{t o_{k}}

sub_v = 1 + sub_{to_1} + sub_{to_2} + ... + sub_{to_k}

$v$ təpəsi ağacın centroidu yalnız və yalnız aşağıda göstərilən halda olur:

hər bir övladı $t o$ üçün $s u b [t o] \leq n /2$ sub[to] \le n / 2;
əgər ağacdan $v$ ilə kök olan alt ağacı silsək, $n - s u b [v] \leq n /2$ n - sub[v] \le n / 2 olacaq, yəni $n /2$ -dən çox təpə qalmayacaq;

Məsələn, sağda təsvir edilmiş $n = 5$ n = 5 təpədən ibarət olan ağacda centroid 2-cı təpə olacaq, çünki

$s u b [4] = 2 \leq n /2$ sub[4] = 2 \le n / 2;
$s u b [3] = 1 \leq n /2$ sub[3] = 1 \le n / 2;
$n - s u b [2] = 5 - 4 = 1 \leq n /2$ n - sub[2] = 5 - 4 = 1 ≤ n / 2;

Nümunə

Nümunədəki ağaca baxaq. 6-cı təpə centroiddur.

Alqoritmin həyata keçirilməsi

Qrafi qonşuluq siyahısında $g$ saxlayarıq.

vector<vector<int>> g;

dfs funksiyası $v$ ilə alt ağacda olan təpələrin sayını qaytarır və bu dəyəri $s u b [v]$ -də saxlayır.

int dfs(int v, int p = -1)
{
  sub[v] = 1;
  for (int to : g[v])
    if (to != p) sub[v] += dfs(to, v);
  return sub[v];
}

C++

centroid funksiyası dərinlik üzrə axtarış aparır, centroidları tapır və $ce n t r$ massivinə yükləyir.

void centroid(int v, int p = -1)
{

Vəhazərin centroid olduğunu yoxlamaq üçün $f l a g = 1$ flag = 1 olaraq işarələyək.

  int flag = 1;

$v$ ilə qonşu olan təpələri $t o$ kontrol edirik. $v \to t o$ v → to kəsməyi nəzərə alırıq.

  for (int to : g[v])
    if (to != p)
    {

Əgər $t o$ övladı üçün $s u b [t o] > n /2$ sub[to] > n / 2 doğru olarsa, onda $v$ centroid deyil.

      if (sub[to] > n / 2) flag = 0;

Əgər $t o$ övladı üçün $s u b [t o] < n /2$ sub[to] < n / 2 doğru olarsa, bu halda $t o$ kök olan alt ağacda heç bir centroid yoxdur. Sonda axtarışı yalnız $s u b [t o] \geq n /2$ sub[to] \ge n / 2 halda davam etmək məntiqli olur.

      if (sub[to] >= n / 2) centroid(to, v);
    }

Ağac $n - s u b [v]$ n - sub[v] təpəsiz qalıb. Əgər bu, $n /2$ -dən çox təpəyə malikdirsə, $v$ centroid deyil.

  if (n - sub[v] > n / 2) flag = 0;

Əgər $v$ təpəsi üçün bütün centroid şərtləri doğru olarsa, o $ce n t r$ massivinə daxil edilir.

  if (flag) centr.push_back(v);
}

Proqramın əsas hissəsi. Massivləri initialize edirik.

scanf("%d", &n);
g.resize(n + 1);
sub.resize(n + 1);

Giriş qrafını oxuyuruq.

for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Dərinlik üzrə axtarış başladırıq, ağacın centroidlarını axtarırıq.

dfs(1);
centroid(1);

Bir centroid-i çıxışdırıq.

printf("%d\n", centr[0]);

Alqoritmin həyata keçirilməsi — ikinci həll yolu

Hər bir təpə üçün $v$ axtarışı dərinlik üzrə $df s (v)$ başlayır, hansı ki aşağıdakı dəyərləri hesablayır:

$s u b [v]$ $v$ ilə alt ağacdakı təpələrin sayını ehtiva edir;
$f [v]$ $v$ təpəsinin bütün alt ağaclar arasında maksimal alt ağac ölçüsünü ehtiva edir, bu ölçü daxil olmaqla $v$ -nin valideyn təpəsini də ehtiva edir.

O halda centroid, $v$ təpəsi olacaq ki, $f [v]$ -nin ən kiçik dəyərinə malikdir. Bu ağacda bir və ya iki belə təpə ola bilər.

$v = 6$ v = 6 təpəsi $1, 2, 3$ və $5$ ölçü olan alt ağaclarla bağlıdır. $f [6] = 5$ f[6] = 5 dəyəri maksimal alt ağac ölçüsüdür.

Eyni zamanda $f$ massivində ən aşağı dəyər $f [6] = 5$ f[6] = 5-dir. Buna görə $6$ təpəsi centroid kimi təsbit edilmişdir.

İki centroid olan ağacın nişanlamasını nəzərdən keçirin.

İki təpə $f$ massivində ən kiçik dəyərə malikdir: $f [1] = 3$ f[1] = 3 və $f [2] = 3$ f[2] = 3.

void dfs(int v, int p = -1)
{
  sub[v] = 1;
  f[v] = 0;
  for (int to : g[v])
    if (to != p)
    {
      dfs(to, v);
      sub[v] += sub[to];
      f[v] = max(f[v], sub[to]);
    }
  f[v] = max(f[v], n - sub[v]);
  if ((root == 0) || (f[v] < f[root])) root = v;
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Massivləri initialize edirik.

scanf("%d", &n);
g.resize(n + 1);
f.resize(n + 1);
sub.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

C++

Dərinlik üzrə axtarış başladırıq, ağacın kök olan bir centroidini çıxışda veririk.

root = 0;
dfs(1);
printf("%d\n", root);

Python realizasiyası

Stack ölçüsünü artırırıq.

import sys
sys.setrecursionlimit(300000)

dfs funksiyası $v$ ilə alt ağacda olan təpələrin sayını qaytarır və bu dəyəri $s u b [v]$ -də saxlayır.

def dfs(v, p = -1):
  sub[v] = 1
  for to in g[v]:
    if to != p:
      sub[v] += dfs(to, v)
  return sub[v]

centroid funksiyası dərinlik üzrə axtarış aparır, centroidları tapır və $ce n t r$ massivinə yükləyir.

def find_centroid(v, p = -1):

Vəhazərin centroid olduğunu yoxlamaq üçün $f l a g = T r u e$ flag = True olaraq işarələyək.

  flag = True

$v$ ilə qonşu olan təpələri $t o$ kontrol edirik. $v \to t o$ v → to kəsməyi nəzərə alırıq.

  for to in g[v]:
    if to == p: continue

Əgər $t o$ övladı üçün $s u b [t o] > n /2$ sub[to] > n / 2 doğru olarsa, $v$ centroid deyil.

    if sub[to] > n // 2:
      flag = False

Əgər $t o$ övladı üçün $s u b [t o] < n /2$ sub[to] < n / 2 doğru olarsa, bu halda $t o$ kök olan alt ağacda heç bir centroid yoxdur. Sonda axtarışı yalnız $s u b [t o] \geq n //2$ sub[to] \ge n // 2 halda davam etmək məntiqli olur.

    if sub[to] >= n // 2:
      find_centroid(to, v)

Ağac $n - s u b [v]$ n - sub[v] təpəsiz qalıb. Əgər bu, $n /2$ -dən çox təpəyə malikdirsə, $v$ centroid deyil.

  if n - sub[v] > n // 2:
      flag = False

Əgər $v$ təpəsi üçün bütün centroid şərtləri doğru olarsa, o $ce n t r$ massivinə daxil edilir.

  if flag: centr.append(v)

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Massivləri initialize edirik.

n = int(input())
g = [[] for _ in range(n + 1)]
sub = [0] * (n + 1)
centr = []

Giriş qrafını oxuyuruq.

for i in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Dərinlik üzrə axtarış başladırıq, ağacın centroidlarını axtarırıq.

dfs(1)
find_centroid(1)

Bir centroid-i çıxışdırıq.

print(centr[0])

Python realizasiyası — ikinci həll yolu

Stack ölçüsünü artırırıq.

import sys
sys.setrecursionlimit(200000)

Hər bir təpə üçün $v$ axtarışı dərinlik üzrə $df s (v)$ başlayır, hansı ki aşağıdakı dəyərləri hesablayır:

$s u b [v]$ $v$ ilə alt ağacdakı təpələrin sayını ehtiva edir;
$f [v]$ $v$ təpəsinin bütün alt ağaclar arasında maksimal alt ağac ölçüsünü ehtiva edir, bu ölçü daxil olmaqla $v$ -nin valideyn təpəsini də ehtiva edir.

O halda centroid, $v$ təpəsi olacaq ki, $f [v]$ -nin ən kiçik dəyərinə malikdir. Bu ağacda bir və ya iki belə təpə ola bilər.

def dfs(v, p=-1):
  global root
  sub[v] = 1
  f[v] = 0
  for to in g[v]:
    if to != p:
      dfs(to, v)
      sub[v] += sub[to]
      f[v] = max(f[v], sub[to])
  f[v] = max(f[v], n - sub[v])
  if root == 0 or f[v] < f[root]:
    root = v

Python

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Massivləri initialize edirik.

n = int(input())
g = [[] for _ in range(n + 1)]
f = [0] * (n + 1)
sub = [0] * (n + 1)

for _ in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Python

Dərinlik üzrə axtarış başladırıq, ağacın kök olan bir centroidini çıxışda veririk.

root = 0
dfs(1)
print(root)