Uzun yol#11452

Uzun yol (Həll təhlili)

Qrafın topoloji sıralamasını tapaq. $d p [u]$ ilə $u$ təpəsindən başlayaraq yol boyunca ziyarət edilə biləcək maksimum şəhər sayını göstərək.

Təpələri topoloji sıralama ardıcıllığında nəzərdən keçirək. $u$ cari təpə olsun. $v_{1}, v_{2}, ..., v_{k}$ v_1, v_2, ..., v_k ilə $u$ -dan çıxan kənarların apardığı təpələri göstərək. Beləliklə, aşağıdakı dəyəri yeniləyək:

d p [u] = ma x (d p [v_{i}] + 1), 1 \leq i \leq k

dp[u] = max(dp[v_i] + 1), 1 \le i \le k

Əvvəlcə $d p [u] = 0 (1 \leq u \leq n)$ dp[u] = 0~(1 \le u \le n) quraraq başlayırıq.

Bütün təpələri işlətdikdən sonra $d p$ massivində ən böyük dəyəri tapırıq. Bu, qrafda ən uzun yolun uzunluğuna bərabərdir.

Nümunə

Solda birinci nümunədən qraf göstərilmişdir. Sağda isə ikincidən. Ən uzun yollar vurğulanmışdır.

Birinci nümunədə ən uzun yol $d p_{1} = 3$ dp_1 = 3-ə bərabərdir.

İkinci nümunədə ən uzun yol $d p_{4} = 2$ dp_4 = 2-ə bərabərdir.

Alqoritmanın reallaşdırılması

Qrafın əlaqə siyahısını elan edək $g$ .

vector<vector<int> > g;

dfs funksiyası $v$ təpəsindən başlayaraq dərinlik üzrə axtarış icra edir. Qraf təpələrini topoloji olaraq sıralayır və onları $t o p$ massivinə yazır.

void dfs(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (used[to] == 0) dfs(to);
  top.push_back(v);
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Yönümlü qrafın əlaqə siyahısını qururuq.

scanf("%d %d", &n, &m);
g.resize(n + 1);
while (m--)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
}

C++

Əlaqəsiz qrafda axtarış icra edirik.

used.resize(n + 1);
for (i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Topoloji sıralamaya əks şəkildə qrafın təpələrini nəzərdən keçiririk, yəni $t o p$ massivinin elementlərini soldan sağa doğru mətrix edirik.

dp.resize(n + 1);
for (int u : top)
{

$u$ təpəsindən özünə yolun uzunluğu $0$ -dəkdir (başlatma).

  dp[u] = 0;

$u$ ilə əlaqəli olan $v$ təpələrini nəzərdən keçirək. $(u, v)$ kənarını nəzərdən keçiririk.

  for (int v : g[u])

Bütün belə $v$ təpələri üçün $d p [v] + 1$ dp[v] + 1 qiymətləri arasında maksimumu axtarırıq.

    dp[u] = max(dp[u], dp[v] + 1);
}

$d p$ massivində ən böyük elementi tapır və çıxış edirik. Bu, qrafdakı ən uzun yolun uzunluğuna uyğundur.

res = *max_element(dp.begin(), dp.end());
printf("%d\n", res);