MuTub (Gümüş)#10422

MuTub (Gümüş) (Həll təhlili)

Hər bir $(k_{i}, v_{i})$ (k_i, v_i) cütündən ibarət olan sorğu üçün $v_{i}$ v_i təpəsindən başlayaraq dərinlik üzrə (DFS) və ya enlik üzrə (BFS) axtarış başlatacağıq. Bu müddətdə, yalnız əlaqəliliyi $k_{i}$ k_i-dən az olmayan kənarlarla qrafda hərəkət edəcəyik. Başlanğıc təpəsi $v_{i}$ v_i çıxılmaqla çatan təpələrin sayını $r es$ kimi hesablayacağıq. $r es$ dəyəri $(k_{i}, v_{i})$ (k_i, v_i) sorğusunun cavabı olacaq.

Nümunə

Fərmer John videolar arasında aşağıdakı əlaqələri qurmuşdur:

Video $1$ və $2$ -nin əlaqəliliyi $3$ -dür,
Video $2$ və $3$ -ün əlaqəliliyi $2$ -dir,
Video $2$ və $4$ -ün əlaqəliliyi $4$ -dür.

Bu məlumatlar əsasında digər video cütlükləri arasında əlaqəlilik hesablana bilər:

Video $1$ və $3$ : əlaqəlilik = $min (3, 2) = 2$ min(3, 2) = 2,
Video $1$ və $4$ : əlaqəlilik = $min (3, 4) = 3$ min(3, 4) = 3,
Video $3$ və $4$ : əlaqəlilik = $min (2, 4) = 2$ min(2, 4) = 2.

İndi aşağıdakı sorğular üçün hansı videoların tövsiyə ediləcəyinə baxaq:

Video $2$ -dən $k = 1$ k = 1 zamanı videolar $1, 3$ və $4$ tövsiyə edilir.
Video $1$ -dən $k = 3$ k = 3 zamanı videolar $2$ və $4$ tövsiyə edilir.
Video $1$ -dən $k = 4$ k = 4 zamanı heç bir video tövsiyə edilmir.

Alqoritmin İcrası — Enlik üzrə Axtarış

Daxil olunan qrafı qonşuluq siyahısında saxlayırıq $g$ .

vector<vector<pair<int, int>>> g;

bfs funksiyası başlanğıc nöqtəsi $s t a r t$ olan və özündən ayrı $s t a r t$ təpəsini qaytaran enlik üzrə axtarış həyata keçirir. Axtarış zamanı yalnız $k$ -dən az olmayan kənarlarla hərəkət edirik.

int bfs(int start, int k)
{

Bu məsələdə ən qısa məsafə arrayına ehtiyac yoxdur — yalnız nöqtənin ziyarət olunub-olunmadığını izləmək kifayətdir. Əgər $i$ nöqtəsi ziyarət olunarsa, $u se d [i] = 1$ used[i] = 1 təyin edirik.

  vector<int> used(n + 1);
  used[start] = 1;

Növbəni başlatırıq və başlanğıc nöqtəsi $s t a r t$ -ı ona əlavə edirik.

  queue<int> q;
  q.push(start);

Enlik üzrə axtarış zamanı ənki nöqtələrinin sayını (başlanğıc nöqtəsi $s t a r t$ -ı saymamaqla) $r es$ dəyişənində hesablayırıq.

  int res = 0;

Enlik üzrə axtarışa başlayırıq.

  while (!q.empty())
  {

Nöqtəni $v$ növbədən çıxarırıq $q$ .

    int v = q.front(); q.pop();

Nöqtə $v$ ilə yaxından əlaqəli olan kənarları nəzərdən keçiririk.

    for (auto edge : g[v])
    {

$(v, t o)$ (v, to) kənarını $k t o$ çəkisi ilə nəzərdən keçiririk.

     int to = edge.first;
     int kto = edge.second;

Əgər $k t o$ çəki kənarı $k$ -dən azdırsa, bu kənarı nəzərə almırıq (bu yolla keçişə icazə verilmir).

      if (kto < k) continue;

Əgər $t o$ təpəsi hələ ziyarət olunmayıbsa, növbəyə əlavə edirik, ziyarət olunmuş kimi qeyd edirik və ziyarət olunmuş təpələrin sayını $r es$ -də $1$ artırırıq.

      if (used[to] == 0)
      {
        q.push(to);
        used[to] = 1;
        res++;
      }
    }
  }

C++

Sorğuya cavab qaytarırıq.

  return res;
}

Proqramın əsas hissəsi. Daxil verilənləri oxuyuruq.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Qonşuluq siyahısına yönləndirilməmiş $(p, q)$ kənarını çəki $r$ ilə əlavə edirik.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Sonra $q u$ sorğuları ardıcıl emal edirik.

while (qu--)
{
  scanf("%d %d", &k, &v);

Başlanğıc təpəsi $v$ ilə enlik üzrə axtarışa başlayırıq. Enlik üzrə axtarış nəticəsində ziyarət olunan təpələrin sayını çap edirik.

  printf("%d\n", bfs(v, k));
}

Alqoritmin İcrası – Dərinlik üzrə Axtarış

Daxil olunan qrafı qonşuluq siyahısında saxlayırıq $g$ .

vector<vector<pair<int, int>>> g;

dfs funksiyası başlanğıc nöqtəsi $v$ başlamaqla dərinlik üzrə axtarış edir və ziyarət olunan nöqtələrin sayını qaytarır. Axtarış zamanı yalnız çəki $k$ -dən az olmayan kənarlarla hərəkət edirik.

int dfs(int v, int k)
{

Təpə $v$ ziyarət olunmuş kimi qeyd edilir.

  used[v] = 1;

Dərinlik üzrə axtarış icrasında kök $v$ ilə altqrafda ziyarət olunmuş təpələrin sayını $r es$ -də hesablayırıq.

  int res = 1;

Nöqtə $v$ ilə əlaqəli kənarları nəzərdən keçiririk.

  for (auto edge : g[v])
  {

$(v, t o)$ (v, to) kənarını $k t o$ çəkisi ilə nəzərdən keçiririk.

    int to = edge.first;
    int kto = edge.second;

Əgər $k t o$ çəki kənarı $k$ -dən azdırsa, bu kənarı nəzərə almırıq (bu yolla keçişə icazə verilmir).

    if (kto < k) continue;

Əgər $t o$ nöqtəsi hələ ziyarət olunmayıbsa, dərinlik üzrə axtarışa buradan başlayırıq. Kök $t o$ ilə altqrafda ziyarət olunmuş təpələrin sayını $r es$ -ə əlavə edirik.

    if (used[to] == 0)
      res += dfs(to, k);
  }
  return res;
}

Proqramın əsas hissəsi. Daxil verilənləri oxuyuruq.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Qonşuluq siyahısına yönləndirilməmiş $(p, q)$ kənarını çəki $r$ ilə əlavə edirik.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Sonra $q u$ sorğuları ardıcıl emal edirik.

while (qu--)
{
  scanf("%d %d", &k, &v);

Başlanğıc nöqtəsi $v$ ilə dərinlik üzrə axtarışa başlayırıq. Dərinlik üzrə axtarış nəticəsində ziyarət olunan təpələrin sayını çap edirik, başlanğıc nöqtəsi $v$ çıxılmaqla.

  used.assign(n + 1, 0);
  printf("%d\n", dfs(v, k) - 1);
}