Ağacda Məsafə I (Həll təhlili)

Ağacın diametrini iki dəfə dərinlik birinci axtarışı (DFS) ilə tapın.

Çünki ağac əlaqəli bir dövrsüz qrafdir, həm dərinlik birinci axtarışı (DFS), həm də eninə birinci axtarışı (BFS) başlanğıc vertex-dən digər bütün vertexlərə ən qısa məsafələri düzgün tapır.

$a$ və $b$ iki zirvə olsun ki, aralarındakı məsafə maksimum olsun — yəni ağacın diametrini təşkil edən zirvələr.

Vertex $a$-dan digər bütün zirvələrə ən qısa məsafələri hesablayaq və onları $dista$ massivinə, vertex $b$-dən isə $distb$ massivinə qeyd edək.

Beləliklə, hər bir zirvə üçün uzaq gələcək zirvəyə qədər olan ən böyük məsafə belə olur

Misal

Misal üçün verilmiş ağacı nəzərdən keçirək.

Ağacın diametri məsələn, $2$ və $5$ zirvələri arasında ola bilər.

Alqoritmin həyata keçirilməsi

Girişdəki ağac qonşuluq listi $g$ şəklində verilir.

$a$ və $b$ zirvələrindən olan ən qısa məsafələr $dista$ və $distb$ massivlərində saxlanılır.

vector<vector<int>> g;
vector<int> dista, distb;

dfs funksiyası vertex $v$-dən dərinlik birinci axtarışı həyata keçirir.

• $d$ parametri mənbədən $v$ vertexinə qədər olan ən qısa məsafəni göstərir.

• Nəticələr $dist$ massivində saxlanılır.

• $p$ parametri alqoritm tamamlama müddətində $v$ vertexinin atası olan vertexi göstərir.

void dfs(int v, int d, vector<int>& dist, int p = -1)
{

dist[v]-də mənbədən $v$ vertexinə qədər olan ən qısa məsafəni qeyd edirik.

  dist[v] = d;

Bütün kənarları (v, to) araşdırırıq. $v$ vertexinin oğlu olan hər bir $to$ vertexi üçün (vertex $to$ vertex $v$-nin atası deyil) dərinlik birinci axtarışı həyata keçiririk.

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, dist, v);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Qeyri-istiqatlı ağac yaradırıq.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

$1$ zirvəsindən olan ən qısa məsafələri tapırıq. Ondan ən uzaq olan zirvə $a$ zirvəsidir.

dfs(1, 0, dista, -1);
a = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Sonra $a$ zirvəsindən olan ən qısa məsafələri hesablayaq və onları $dista$ massivində saxlayırıq. $a$-dan ən uzaq olan zirvə $b$ zirvəsidir. $a$ və $b$ zirvələri arasındakı məsafə ağacın diametridir.

dfs(a, 0, dista, -1);
b = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

$b$ zirvəsindən olan ən qısa məsafələri hesablayaq və onları $distb$ massivində saxlayırıq.

dfs(b, 0, distb, -1);

Hər bir zirvə $i$ üçün ən uzaq zirvəyə qədər olan məsafəni çap edirik.

for (i = 1; i <= n; i++)
  printf("%d ", max(dista[i], distb[i]));
printf("\n");

Python tətbiqi

Rekursiya üçün steki artırın.

import sys
sys.setrecursionlimit(1000000)

dfs funksiyası vertex $v$-dən dərinlik birinci axtarışı həyata keçirir.

• $d$ parametri mənbədən $v$ vertexinə qədər olan ən qısa məsafəni göstərir.

• Nəticələr $dist$ massivində saxlanılır.

• $p$ parametri alqoritm tamamlama müddətində $v$ vertexinin atası olan vertexi göstərir.

def dfs(v, d, dist, p =- 1):

dist[v]-də mənbədən $v$ vertexinə qədər olan ən qısa məsafəni qeyd edirik.

  dist[v] = d

Bütün kənarları (v, to) araşdırırıq. $v$ vertexinin oğlu olan hər bir $to$ vertexi üçün (vertex $to$ vertex $v$-nin atası deyil) dərinlik birinci axtarışı həyata keçiririk.

  for to in g[v]:
    if to != p:
      dfs(to, d + 1, dist, v)

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Qeyri-istiqatlı ağac yaradırıq.

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

$1$ zirvəsindən olan ən qısa məsafələri tapırıq. Ondan ən uzaq olan zirvə $a$ zirvəsidir.

dfs(1, 0, dista)
a = dista.index(max(dista[1:]))

Sonra $a$ zirvəsindən olan ən qısa məsafələri hesablayaq və onları $dista$ massivində saxlayırıq. $a$-dan ən uzaq olan zirvə $b$ zirvəsidir. $a$ və $b$ zirvələri arasındakı məsafə ağacın diametridir.

dfs(a, 0, dista)
b = dista.index(max(dista[1:]))

$b$ zirvəsindən olan ən qısa məsafələri hesablayaq və onları $distb$ massivində saxlayırıq.

dfs(b, 0, distb)

Hər bir zirvə $i$ üçün ən uzaq zirvəyə qədər olan məsafəni çap edirik.

result = [max(dista[i], distb[i]) for i in range(1, n + 1)]
print(*result)