Körpülər#1943

Körpülər (Həll təhlili)

Körpü adlanan kənar, silindikdə qrafın əlaqəli komponentlərinin sayını artıran kənardır. Kənar o zaman və yalnız o zaman körpüdür ki, o, heç bir sadə dövrün üzərində yerləşməsin: əgər kənar dövrə aiddirsə, onda silindikdən sonra kənarın uc nöqtələri dövrün qalan hissəsi vasitəsilə əlaqəli qalır.

Dərinliyinə axtarışı işə salaq. Qrafın hər bir kənarı ya axtarış ağacının kənarı, ya da əks kənar olacaq. Əks kənar onun uc nöqtələri arasındakı ağac üzrə yol ilə birlikdə dövr əmələ gətirir, buna görə də o, körpü ola bilməz. Deməli, körpü yalnız axtarış ağacının kənarları ola bilər.

Axtarış zamanı hər bir $v$ təpəsi üçün iki etiket hesablayaq:

$d [v]$ — $v$ təpəsinə giriş vaxtı, yəni $v$ təpəsinin ilk dəfə ziyarət edildiyi sıra nömrəsi;
$u p [v]$ — $v$ təpəsindən ağacın kənarları ilə onun törəmələrinə enərək və sonra ən çox bir əks kənardan keçərək əldə edilə bilən ən kiçik giriş vaxtı.

$(v, t o)$ (v, to) ağac kənarına baxaq, burada $t o$ — $v$ təpəsinin oğludur. Üç hal mümkündür:

$u p [t o] < d [v]$ up[to] < d[v]. $t o$ alt ağacının hansısa təpəsindən $v$ təpəsinin öz əcdadına əks kənar gedir. Başqa sözlə, $v$ təpəsindən və ya onun törəməsindən $v$ -nin əcdadına əks kənar o zaman və yalnız o zaman mövcuddur ki, $v$ -nin elə $t o$ oğlu tapılsın ki, $u p [t o] < d [v]$ up[to] < d[v] olsun.
$u p [t o] = d [v]$ up[to] = d[v]. $t o$ alt ağacı məhz $v$ təpəsinə gedən əks kənar saxlayır.
$u p [t o] > d [v]$ up[to] > d[v]. $t o$ alt ağacının heç bir təpəsi $(v, t o)$ (v, to) kənarından keçmədən $v$ təpəsinə və ya onun əcdadlarına çata bilmir. Deməli, $(v, t o)$ (v, to) kənarı körpüdür.

İlk iki halda $(v, t o)$ (v, to) kənarı dövrün üzərində yerləşir və körpü deyil. Beləliklə, aşağıdakı meyarı alırıq:

Teorem. Axtarış ağacının $(v, t o)$ (v, to) kənarı, burada $t o$ — $v$ təpəsinin oğludur, o zaman və yalnız o zaman körpüdür ki, $u p [t o] > d [v]$ up[to] > d[v] olsun.

Dərinliyinə axtarış $O (n + m)$ O(n + m) vaxtında yerinə yetirilir. Tapılmış körpülərin nömrələri çıxışdan əvvəl sıralanır.

Misal

Misalda verilmiş qraf aşağıdakı görünüşə malikdir. Hər bir kənarın yanında onun giriş məlumatlarındakı nömrəsi göstərilib:

$1$ təpəsindən dərinliyinə axtarışı işə salaq. Hər bir təpənin qonşularını giriş məlumatlarında kənarların görünmə sırası ilə nəzərdən keçirəcəyik. Gəzinti təpələri $1, 2, 3, 4, 5, 6$ 1, 2, 3, 4, 5, 6 sırası ilə ziyarət edir. Axtarış ağacının kənarları $1, 2, 3, 5$ 1, 2, 3, 5 və $7$ nömrəli kənarlar olur, $4 = (3, 1)$ 4 = (3, 1) və $6 = (6, 4)$ 6 = (6, 4) kənarları isə əks kənarlar olur.

Ağacın bütün kənarları üçün $u p [t o] > d [v]$ up[to] > d[v] şərtini yoxlayaq:

Kənar $(v, t o)$ (v, to)	Nömrə	$u p [t o]$	$d [v]$	Nəticə
$(1, 2)$	1	1	1	$u p [2] = d [1]$ up[2] = d[1], körpü deyil
$(2, 3)$	2	1	2	$u p [3] < d [2]$ up[3] < d[2], körpü deyil
$(3, 4)$	3	4	3	$u p [4] > d [3]$ up[4] > d[3], körpü
$(4, 5)$	5	4	4	$u p [5] = d [4]$ up[5] = d[4], körpü deyil
$(5, 6)$	7	4	5	$u p [6] < d [5]$ up[6] < d[5], körpü deyil

Beləliklə, qrafda düz bir körpü var — $3$ və $4$ təpələrini birləşdirən $3$ nömrəli kənar.

Alqoritmin reallaşdırılması

Qrafı qonşuluq siyahısı $g$ şəklində saxlayırıq. Hər bir $v$ təpəsi üçün $g [v]$ -də $(t o, i d)$ (to, id) cütləri yazılır, burada $t o$ — qonşu təpə, $i d$ isə $(v, t o)$ (v, to) kənarının giriş məlumatlarındakı nömrəsidir. Kənarın nömrəsi iki səbəbə görə lazımdır: gəzinti zamanı gəldiyimiz eyni kənarla geri qayıtmamaq üçün və körpüləri təpə cütləri kimi deyil, giriş kənarlarının nömrələri kimi çıxarmaq üçün.

$d$ və $u p$ massivləri $d [v]$ və $u p [v]$ etiketlərini saxlayır. $d [v]$ -nin sıfır qiyməti $v$ təpəsinin hələ ziyarət edilmədiyini bildirir. $b r i d g es$ bridges massivində körpü olan kənarların nömrələrini toplayırıq.

vector<vector<pair<int, int> > > g;
vector<int> d, up, bridges;

dfs funksiyası $v$ təpəsindən dərinliyinə axtarışı reallaşdırır. $p$ parametri — içinə $v$ təpəsinə gəldiyimiz kənarın nömrəsidir. Axtarış ağacının kökü üçün belə kənar olmadığından, defolt olaraq $p = - 1$ p = -1 götürülür. Təpəyə girişdə $d [v]$ və $u p [v]$ -yə cari vaxtı təyin edirik.

void dfs(int v, int p = -1)
{
  d[v] = up[v] = timer++;

$v$ təpəsindən çıxan bütün $(v, t o)$ (v, to) kənarlarını nəzərdən keçiririk. $p$ nömrəli kənarı ötürürük: biz bu kənarla $v$ -yə gəlmişik, və o, valideynə aparır.

  for (auto edge : g[v])
  {
    int to = edge.first;
    int id = edge.second;
    if (id == p) continue;

Əgər $t o$ təpəsi artıq ziyarət edilibsə $(d [t o] \neq = 0)$ (d[to] \ne 0), onda $(v, t o)$ (v, to) — əks kənardır. $u p [v]$ -ni $t o$ -ya giriş vaxtını nəzərə alaraq yenidən hesablayırıq.

    if (d[to] != 0)
      up[v] = min(up[v], d[to]);

Əks halda $(v, t o)$ (v, to) — ağac kənarıdır. $i d$ kənarının nömrəsini ötürərək $t o$ təpəsindən axtarışı işə salırıq. Geri qayıtdıqdan sonra $u p [v]$ -ni $u p [t o]$ vasitəsilə yenidən hesablayırıq.

    else
    {
      dfs(to, id);
      up[v] = min(up[v], up[to]);

Əgər $u p [t o] > d [v]$ up[to] > d[v] olarsa, onda $t o$ alt ağacından $(v, t o)$ (v, to) kənarından keçmədən $v$ -yə və ya onun əcdadlarına düşmək mümkün deyil, buna görə də $i d$ nömrəli kənar körpüdür.

      if (up[to] > d[v]) bridges.push_back(id);
    }
  }
}

Proqramın əsas hissəsi. Giriş qrafını oxuyuruq. Hər bir $(a, b)$ kənarını onun $i$ nömrəsi ilə birlikdə hər iki təpənin qonşuluq siyahısına əlavə edirik.

scanf("%d %d", &n, &m);
g.resize(n + 1);
for (i = 1; i <= m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(make_pair(b, i));
  g[b].push_back(make_pair(a, i));
}

C++

Etiket massivlərini işə salırıq.

d.resize(n + 1);
up.resize(n + 1);

$t im er$ dəyişəni axtarışın cari vaxtını saxlayır.

timer = 1;

Qraf əlaqəli olmaya bilər, buna görə də hələ ziyarət edilməmiş hər bir təpədən dərinliyinə axtarışı işə salırıq.

for (i = 1; i <= n; i++)
  if (d[i] == 0) dfs(i);

Körpülərin nömrələrini artan sıra ilə sıralayırıq.

sort(bridges.begin(), bridges.end());

Körpülərin sayını, növbəti sətirdə isə onların nömrələrini çıxarırıq.

printf("%d\n", bridges.size());
for (i = 0; i < bridges.size(); i++)
  printf("%d ", bridges[i]);
printf("\n");