Ağacın diametri (Həll təhlili)

Ağacın diametri ağacdakı ən uzun yolun uzunluğudur. Başqa sözlə, aralarındakı məsafə maksimal olan iki $a$ və $b$ təpəsini tapmalıyıq.

Bu məsələni həll etmək üçün aşağıdakı alqoritmdən istifadə edək:

• Əvvəlcə ağacın istənilən təpəsindən, məsələn $1$-ci təpədən başlayaraq dərinliyinə axtarış aparaq. Bu gəzinti zamanı başlanğıc nöqtədən maksimal məsafədə olan təpəni tapın. Bu təpəni $a$ ilə işarə edin.

• Sonra, bu dəfə $a$ təpəsindən başlayaraq yenidən dərinliyinə axtarış aparın. Bu gəzintinin nəticəsində $a$-dan ən uzaqda olan təpəni tapın və onu $b$ ilə işarə edin.

Bu zaman $a$ və $b$ təpələri arasındakı məsafə ağacdakı bütün təpə cütləri arasında maksimaldır və deməli, ağacın diametrinə bərabərdir.

Misal

Misaldan olan ağacı nəzərdən keçirək.

Ağacın diametri $3$-dür. Maksimal məsafəyə, məsələn, $2$ və $5$ təpələri arasında nail olunur.

Tapşırıq

Ağacın diametrini tapın.

Alqoritmin implementasiyası

Giriş ağacını $g$ qonşuluq siyahısında saxlayın. Mənbədən hər bir təpəyə qədər olan ən qısa məsafələri $dist$ massivində saxlayın.

vector<vector<int>> g;
vector<int> dist;

dfs funksiyası $v$ təpəsindən dərinliyinə axtarış həyata keçirir. Mənbədən $v$ təpəsinə qədər olan ən qısa məsafə $d$-dir. Dərinliyinə axtarış zamanı $v$ təpəsinin valideyni $p$-dir.

void dfs(int v, int d, int p = -1)
{

Mənbədən $v$ təpəsinə qədər olan ən qısa məsafəni dist[v]-də saxlayın.

  dist[v] = d;

(v, to) bütün qırağları üzərindən gedin. $v$ təpəsinin hər bir oğlu üçün ($to$ $v$-nin valideyni olmadıqda) dərinliyinə axtarışı başladın. Mənbədən $to$ təpəsinə qədər olan məsafə d + 1 olacaq.

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

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

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

İstiqamətləndirilməmiş ağac qurun.

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

$1$-ci təpədən bütün digər təpələrə qədər olan ən qısa məsafələri tapın. Ondan ən uzaqda olan təpə $a$-dır.

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

$b$ təpəsindən bütün digər təpələrə qədər olan ən qısa məsafələri tapın. Ondan ən uzaqda olan təpə $b$-dir.

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

Ağacın diametrini — $a$-dan $b$-yə qədər olan ən qısa məsafəni çap edin.

printf("%d\n", dist[b]);