Bakı Metrosu#11865

Bakı Metrosu (Həll təhlili)

Metro sxemi $n$ təpədən və $n$ tilindən ibarət əlaqəli istiqamətləndirilməmiş qrafdır. $n$ təpəsi olan və məhz $n - 1$ n - 1 tilə malik əlaqəli qraf ağacdır. Ağaca daha bir til əlavə etmək məhz bir dövr yaradır. Buna görə də şərtdəki qraf yeganə dövrdən (halqavari xətdən) ibarətdir ki, onun təpələrindən ağaclar (bəlkə də boş) asılmışdır.

Hər bir təpə üçün dövrün ən yaxın təpəsinə qədər olan ən qısa yolun uzunluğunu tapmaq lazımdır. Dövr təpələri üçün cavab $0$ -a bərabərdir. Məsələ iki mərhələdə həll olunur.

1-ci mərhələ. Dövrün ayrılması: yarpaqların ardıcıl silinməsi

Bütün təpələrin dərəcələrini hesablayaq. Dərəcəsi $1$ olan bütün təpələri, yəni yarpaqları, növbəyə yerləşdirək. Növbə boş olmayana qədər, ondan $v$ təpəsini çıxarırıq və onu silinmiş kimi qeyd edirik. Sonra onun hələ silinməmiş hər bir qonşusunun dərəcəsini $1$ azaldırıq. Əgər qonşunun dərəcəsi $1$ -ə bərabər olarsa, deməli o özü yarpağa çevrilib və biz onu növbəyə əlavə edirik.

Proses tamamlandıqdan sonra yalnız dövrün təpələri silinməmiş qalacaq. Bu, iki müşahidədən irəli gəlir:

Dövrün təpəsi heç vaxt yarpağa çevrilməyəcək. Onun həmişə dövr üzrə iki qonşusu var, onlar da silinmir. Bu, prosesin addımları üzrə induksiya ilə ciddi şəkildə sübut olunur.
Asılı ağacın hər bir təpəsi silinəcək. Yarpaqların silinməsi ağacı aşağıdan yuxarıya, yarpaqlardan dövrə bağlanma nöqtəsinə qədər "gəmirir". Bu prosedur Kan alqoritminə əsasən aparılan topoloji sıralamaya analojidir, sadəcə istiqamətləndirilməmiş qrafa tətbiq edilib.

2-ci mərhələ. Çoxmənbəli enlik üzrə axtarış

Bütün dövr təpələri üçün $d [v] = 0$ d[v] = 0 qəbul edək, qalanları üçün isə $d [v] = -1$ d[v] = –1 (ziyarət edilməyib). Bütün dövr təpələrini eyni zamanda növbəyə yerləşdirək və onlardan enlik üzrə axtarışı başladaq. $u$ təpəsi növbədən çıxarıldıqda, onun hər bir ziyarət edilməmiş $w$ qonşusu $d [w] = d [u] + 1$ d[w] = d[u] + 1 qiymətini alır və növbəyə əlavə olunur.

Çoxmənbəli enlik üzrə axtarış təpələri həmin çoxluğa qədər olan məsafənin qeyri-azalan sırası ilə emal edir. Buna görə də $d [v]$ $v$ -dən halqavari xəttə qədər minimal keçid sayına bərabərdir. Dövrdən kənarda olan hər şey ağac olduğu üçün, hər stansiyadan halqaya qədər olan yol əslində yeganədir.

Qrafda dərəcəsi $1$ olan təpələr olduqca, onları siləcəyik.
Belə təpələr qalmadıqda, qrafda yalnız dövr yaradan təpələr qalacaq.

Bu proses tərs topoloji sıralamanı xatırladır: biz yalnız "daxili" təpələr qalana qədər yarpaqları ardıcıl olaraq siririk — məhz onlar da dövrü təşkil edir.

Bundan sonra dövrə daxil olan bütün təpələrdən eyni zamanda enlik üzrə axtarışı işə salırıq. Beləliklə, qalan hər bir təpə üçün halqanın ən yaxın təpəsinə qədər minimal addım (keçid) sayı müəyyən edilir.

Misal

Birinci misalda bütün təpələr bir dövrə daxildir, buna görə də hər biri üçün məsafə $0$ -a bərabərdir.

İkinci misalda dövrü $2, 3$ və $5$ təpələri yaradır, qalan təpələr isə ondan müəyyən məsafədədir.

Alqoritmin reallaşdırılması

Qrafın qonşuluq siyahısını $g$ , həmçinin köməkçi massivləri elan edək:

$u se d$ — təpənin silinmə əlaməti: əgər $v$ təpəsi yarpaq kimi artıq silinibsə $u se d [v] = 1$ used[v] = 1, əgər o hələ qrafda qalırsa $u se d [v] = 0$ used[v] = 0. Birinci mərhələ tamamlandıqdan sonra sıfır qiymətlər yalnız dövr təpələrində saxlanılacaq;
$d i s t$ — məsafələr massivi: $d i s t [v]$ dist[v] $v$ təpəsindən dövrün ən yaxın təpəsinə qədər keçid sayına bərabərdir ( $-1$ qiyməti təpənin hələ ziyarət edilmədiyini bildirir);
$d e g$ — təpələrin cari dərəcələri: $d e g [v]$ deg[v] $v$ təpəsinin hələ silinməmiş qonşularının sayına bərabərdir.

$q$ növbəsi alqoritmin hər iki mərhələsində istifadə olunur: əvvəlcə yarpaqların ardıcıl silinməsi üçün, sonra isə çoxmənbəli enlik üzrə axtarış üçün.

vector\u003cvector\u003cint\u003e \u003e g;
vector\u003cint\u003e used, dist, deg;
queue\u003cint\u003e q;

Giriş məlumatlarını oxuyuruq. Qrafı qururuq.

scanf("%d", \u0026n);
g.resize(n + 1);
for (i = 0; i \u003c n; i++)
{
  scanf("%d %d", \u0026a, \u0026b);
  g[a].push_back(b);
  g[b].push_back(a);
}

C++

Təpələrin ilkin dərəcələrini hesablayırıq: $i$ təpəsinin dərəcəsi onun qonşuluq siyahısının $g [i]$ ölçüsünə bərabərdir. Bütün yarpaqları, yəni dərəcəsi $1$ olan təpələri, $q$ növbəsinə yerləşdiririk və dərhal silinmiş kimi qeyd edirik $(u se d [i] = 1)$ (used[i] = 1).

used.resize(n + 1, 0);
deg.resize(n + 1, 0);
for (i = 1; i \u003c= n; i++)
{
  deg[i] = g[i].size();
  if (deg[i] == 1)
  {
    q.push(i);
    used[i] = 1;
  }
}

C++

Yarpaqları ardıcıl olaraq siririk. Zahirən bu dövr enlik üzrə axtarışa oxşayır, lakin təpə ilk dəfə aşkarlananda deyil, yalnız özü yarpağa çevriləndə növbəyə düşür. Növbədən $v$ təpəsini çıxarırıq və onun $t o$ qonşularını araşdırırıq. Artıq silinmiş kimi qeyd edilmiş qonşuları buraxırıq. Hər bir silinməmiş qonşu üçün dərəcəni $1$ azaldırıq, çünki $(v, t o)$ (v, to) tili $v$ təpəsi ilə birlikdə qrafdan yox olur.

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (used[to] == 0)
    {
      deg[to]--;

C++

Əgər azaldıqdan sonra to təpəsinin dərəcəsi $1$ -ə bərabər olarsa, deməli onun yalnız bir silinməmiş qonşusu qalıb, yəni o özü yarpağa çevrilib. Onu növbəyə yerləşdiririk və silinmiş kimi qeyd edirik. Dövr təpələri heç vaxt $1$ dərəcəsinə çatmır, buna görə də proses halqavari xətdə dayanır.

      if (deg[to] == 1)
      {
        q.push(to);
        used[to] = 1;
      }
    }
}

C++

Bu anda $u se d [i] = 0$ used[i] = 0 bərabərliyi yalnız o halda doğrudur ki, $i$ təpəsi dövrə aiddir.

$d i s t$ massivini $-1$ qiyməti ilə ilkinləşdiririk (bütün təpələr ziyarət edilməyib). Növbə bu anda artıq boşdur, lakin boş növbənin təyin edilməsi ikinci dolanmadan əvvəl onu açıq şəkildə sıfırlayır. Sonra dövrün hər bir təpəsini növbəyə yerləşdiririk və onun üçün $d i s t [i] = 0$ dist[i] = 0 qəbul edirik — halqavari xəttin bütün təpələri eyni zamanda enlik üzrə axtarışın mənbələrinə çevrilir.

dist = vector\u003cint\u003e(n + 1, -1);
q = queue\u003cint\u003e();
for (i = 1; i \u003c= n; i++)

  if (used[i] == 0)
  {
    q.push(i);
    dist[i] = 0;
  }

C++

Çoxmənbəli enlik üzrə axtarışı işə salırıq. Növbədən $v$ təpəsini çıxarırıq. Onun hər bir ziyarət edilməmiş $t o (d i s t [t o] = -1)$ to~(dist[to] = –1) qonşusu $d i s t [v] + 1$ dist[v] + 1 məsafəsini alır və növbəyə əlavə olunur. Dövr təpələri əvvəldən $0$ məsafəsi ilə qeyd edilib, buna görə dolanma halqaya qayıtmır və yalnız asılı ağacların dərinliyinə doğru yayılır. Təpələr növbədən məsafənin qeyri-azalan sırası ilə çıxarıldığı üçün, hər bir $d i s t [t o]$ dist[to] qiyməti ən qısadır.

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (dist[to] == -1)
    {
      q.push(to);
      dist[to] = dist[v] + 1;
    }
  }

C++

Stansiyalardan halqavari xəttə qədər olan məsafələri onların nömrələri sırası ilə çap edirik.

for (i = 1; i \u003c= n; i++)
   printf("%d ", dist[i]);
printf("\n");