Köprüler#1943

Köprüler (Editoryal)

Köprü, kaldırılması grafın bağlı bileşen sayısını artıran kenara denir. Bir kenar ancak ve ancak hiçbir basit çevrim üzerinde yer almıyorsa köprüdür: eğer bir kenar bir çevrime aitse, bu kenar kaldırıldıktan sonra kenarın uç noktaları çevrimin geri kalan kısmı üzerinden bağlı kalır.

Derinlik öncelikli arama (DFS) başlatalım. Graftaki her kenar ya arama ağacının bir kenarı ya da geri kenar (back edge) olacaktır. Geri kenar, uç noktaları arasındaki ağaç yolu ile birlikte bir çevrim oluşturur, bu yüzden köprü olamaz. Dolayısıyla, yalnızca arama ağacının kenarları köprü olabilir.

Arama sırasında her $v$ tepesi için iki etiket hesaplayalım:

$d [v]$ — $v$ tepesine giriş zamanı, yani $v$ tepesinin ilk ziyaret edildiği sıra numarası;
$u p [v]$ — $v$ tepesinden, ağaç kenarları boyunca torunlarına inerek ve ardından en fazla bir geri kenar geçerek ulaşılabilecek en küçük giriş zamanı.

$t o$ 'nun $v$ 'nin çocuğu olduğu $(v, t o)$ (v, to) ağaç kenarını ele alalım. Üç durum mümkündür:

$u p [t o] < d [v]$ up[to] < d[v]. $t o$ alt ağacının bir tepesinden, $v$ 'nin kendi atasına giden bir geri kenar vardır. Başka bir deyişle, $v$ 'den veya onun bir torunundan $v$ 'nin bir atasına giden bir geri kenar bulunması, ancak ve ancak $v$ 'nin $u p [t o] < d [v]$ up[to] < d[v] olan bir $t o$ çocuğu varsa gerçekleşir.
$u p [t o] = d [v]$ up[to] = d[v]. $t o$ alt ağacı, tam olarak $v$ tepesine giden bir geri kenar içerir.
$u p [t o] > d [v]$ up[to] > d[v]. $t o$ alt ağacının hiçbir tepesi, $(v, t o)$ (v, to) kenarından geçmeden $v$ tepesine veya onun atalarına ulaşamaz. Dolayısıyla, $(v, t o)$ (v, to) kenarı bir köprüdür.

İlk iki durumda $(v, t o)$ (v, to) kenarı bir çevrim üzerinde yer alır ve köprü değildir. Böylece şu kriteri elde ederiz:

Teorem. $t o$ 'nun $v$ 'nin çocuğu olduğu $(v, t o)$ (v, to) arama ağacı kenarı, ancak ve ancak $u p [t o] > d [v]$ up[to] > d[v] ise köprüdür.

Derinlik öncelikli arama $O (n + m)$ O(n + m) zamanda çalışır. Bulunan köprülerin numaraları çıktıdan önce sıralanır.

Örnek

Örnekte verilen graf aşağıdaki gibidir. Her kenarın yanında girdi verisindeki numarası belirtilmiştir:

$1$ tepesinden derinlik öncelikli aramayı başlatalım. Her tepenin komşularını girdi verisindeki kenarların görünme sırasına göre inceleyeceğiz. Gezinti, tepeleri $1, 2, 3, 4, 5, 6$ 1, 2, 3, 4, 5, 6 sırasıyla ziyaret eder. Arama ağacının kenarları $1, 2, 3, 5$ 1, 2, 3, 5 ve $7$ numaralı kenarlar olur, $4 = (3, 1)$ 4 = (3, 1) ve $6 = (6, 4)$ 6 = (6, 4) kenarları ise geri kenar olur.

Ağacın tüm kenarları için $u p [t o] > d [v]$ up[to] > d[v] koşulunu kontrol edelim:

Kenar $(v, t o)$ (v, to)	Numara	$u p [t o]$	$d [v]$	Sonuç
$(1, 2)$	1	1	1	$u p [2] = d [1]$ up[2] = d[1], köprü değil
$(2, 3)$	2	1	2	$u p [3] < d [2]$ up[3] < d[2], köprü değil
$(3, 4)$	3	4	3	$u p [4] > d [3]$ up[4] > d[3], köprü
$(4, 5)$	5	4	4	$u p [5] = d [4]$ up[5] = d[4], köprü değil
$(5, 6)$	7	4	5	$u p [6] < d [5]$ up[6] < d[5], köprü değil

Böylece, grafta tam olarak bir köprü vardır — $3$ ve $4$ tepelerini birleştiren $3$ numaralı kenar.

Algoritmanın Gerçeklenmesi

Grafı bir komşuluk listesi $g$ olarak saklıyoruz. Her $v$ tepesi için $g [v]$ içinde $(t o, i d)$ (to, id) çiftleri kayıtlıdır; burada $t o$ — komşu tepe, $i d$ — $(v, t o)$ (v, to) kenarının girdi verisindeki numarasıdır. Kenar numarası iki sebepten gereklidir: gezinti sırasında geldiğimiz kenardan geri dönmemek için ve köprüleri tepe çiftleri olarak değil, girdi kenarlarının numaraları olarak çıktı olarak vermek için.

$d$ ve $u p$ dizileri $d [v]$ ve $u p [v]$ etiketlerini içerir. $d [v]$ 'nin sıfır değeri, $v$ tepesinin henüz ziyaret edilmediği anlamına gelir. $b r i d g es$ bridges dizisinde köprü olan kenarların numaralarını topluyoruz.

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

dfs fonksiyonu, $v$ tepesinden derinlik öncelikli aramayı gerçekleştirir. $p$ parametresi, $v$ tepesine gelmemizi sağlayan kenarın numarasıdır. Arama ağacının kökü için böyle bir kenar yoktur, bu yüzden varsayılan olarak $p = - 1$ p = -1'dir. Bir tepeye girerken $d [v]$ ve $u p [v]$ 'ye geçerli zamanı atarız.

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

$v$ tepesinden çıkan tüm $(v, t o)$ (v, to) kenarlarını geziyoruz. $p$ numaralı kenarı atlıyoruz: bu kenardan $v$ 'ye geldik ve ebeveyne gider.

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

Eğer $t o$ tepesi zaten ziyaret edilmişse $(d [t o] \neq = 0)$ (d[to] \ne 0), o zaman $(v, t o)$ (v, to) — bir geri kenardır. $u p [v]$ 'yi $t o$ 'ya giriş zamanını dikkate alarak yeniden hesaplıyoruz.

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

Aksi halde $(v, t o)$ (v, to) — bir ağaç kenarıdır. $t o$ tepesinden $i d$ kenar numarasını vererek aramayı başlatıyoruz. Geri döndükten sonra $u p [v]$ 'yi $u p [t o]$ üzerinden yeniden hesaplıyoruz.

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

Eğer $u p [t o] > d [v]$ up[to] > d[v] ise, $t o$ alt ağacından $(v, t o)$ (v, to) kenarını kullanmadan $v$ 'ye veya atalarına ulaşmak mümkün değildir, bu yüzden $i d$ numaralı kenar bir köprüdür.

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

Programın ana bölümü. Girdi grafını okuyoruz. Her $(a, b)$ kenarını, $i$ numarasıyla birlikte her iki tepenin komşuluk listelerine ekliyoruz.

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 dizilerini başlatıyoruz.

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

$t im er$ değişkeni, aramanın geçerli zamanını tutar.

timer = 1;

Graf bağlı olmayabilir, bu yüzden henüz ziyaret edilmemiş her tepeden derinlik öncelikli aramayı başlatıyoruz.

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

Köprü numaralarını artan sırada sıralıyoruz.

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

Köprü sayısını, bir sonraki satırda ise numaralarını yazdırıyoruz.

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