Eklem Noktaları (Editoryal)

Eklem noktaları derinlik öncelikli arama (DFS) kullanılarak bulunur. Her $v$ köşesi için iki etiket hesaplanır:

$d [v]$ — derinlik öncelikli arama sırasında $v$ köşesine giriş zamanı;
$u p [v]$ — $v$ köşesi kökünde olan alt ağaçtan, bir geri kenar üzerinden geçilerek ulaşılabilen köşeler arasındaki en küçük giriş zamanı.

Gezinti ağacının kökü olmayan bir $v$ köşesi, gezinti ağacında $u p [t o] \geq d [v]$ up[to] \ge d[v] eşitsizliğinin sağlandığı bir $t o$ çocuğuna sahipse, eklem noktasıdır. Bu eşitsizlik, $t o$ köşesi kökünde olan alt ağaçtan geri kenarlar üzerinden $v$ köşesinden daha yukarıya çıkılamayacağı anlamına gelir. Bu nedenle $v$ silindiğinde bu alt ağaç grafın geri kalanından kopmuş olur.

Gezinti ağacının kökü, ancak ve ancak gezinti ağacında en az iki çocuğu varsa eklem noktasıdır.

Örnek

Örnekteki graf şu şekildedir:

Kalın çizgilerle derinlik öncelikli gezinti ağacının kenarları gösterilmiştir. Her $v$ köşesinin yanında $d [v] / u p [v]$ d[v] / up[v] etiketleri belirtilmiştir. Eklem noktaları renkle vurgulanmıştır.

Köşe 1 — gezinti ağacının köküdür. Gezinti ağacında iki çocuğu olduğu için ( $2$ ve $4$ köşeleri) eklem noktasıdır.
Köşe 2 — eklem noktasıdır, çünkü $(2, 6)$ ağaç kenarı için $u p [6] \geq d [2] (2 \geq 2)$ up[6] \ge d[2]~(2 \ge 2) sağlanır.
Köşe 3 — eklem noktasıdır, çünkü $(3, 8)$ ağaç kenarı için $u p [8] \geq d [3] (3 \geq 3)$ up[8] \ge d[3]~(3 \ge 3) sağlanır.

Algoritmanın Gerçeklenmesi

Graf, $g$ komşuluk listesi şeklinde saklanır. $u se d$ dizisi ziyaret edilmiş köşeleri işaretler, $d$ ve $u p$ dizilerinde aynı adlı etiketler saklanır. $t im er$ değişkeni derinlik öncelikli aramanın güncel zamanını tutar. Bulunan eklem noktaları $A r tP$ kümesinde toplanır: bu küme tekrarları hariç tutar ve köşeleri artan sırada saklar.

vector\<vector\<int\>\> g;
vector\<int\> d, up, used;
set\<int\> ArtP;

dfs fonksiyonu, $v$ köşesinden başlayarak derinlik öncelikli arama yapar ve bu arada eklem noktalarını bulur. $p$ parametresi, $v$ köşesinin gezinti ağacındaki ebeveynidir. Ağacın kökü için $p = - 1$ p = -1 olur, bu varsayılan değerdir.

void dfs(int v, int p = -1)
{

$v$ köşesine girildiğinde, onu ziyaret edilmiş olarak işaretleriz. $d [v]$ ve $u p [v]$ etiketleri, zamanlayıcının güncel değerini alır, bundan sonra zamanlayıcı artırılır.

  used[v] = true;
  d[v] = up[v] = timer++;

$c hi l d r e n$ children değişkeni, $v$ köşesinin gezinti ağacındaki çocuklarını sayar; bu sayı, $v$ köşesinin kök olması durumunda gerekli olacaktır.

  int children = 0;

$v$ köşesine komşu olan $t o$ köşelerini gözden geçiriyoruz. $(v, t o)$ (v, to) kenarı üç türden biri olabilir:

ters yönde incelenen, ebeveyne giden bir ağaç kenarı ( $t o = p$ to = p). Böyle bir kenarı atlıyoruz;
bir geri kenar ( $t o$ köşesi zaten ziyaret edilmiş ve $t o \neq = p$ to \ne p);
henüz ziyaret edilmemiş $t o$ köşesine giden bir ağaç kenarı.

  for (int to : g[v])
  {
    if (to == p) continue;

Eğer $t o$ köşesi zaten ziyaret edilmişse, $(v, t o)$ (v, to) bir geri kenardır. $u p [v]$ değerini yeniden hesaplıyoruz.

    if (used[to])
      up[v] = min(up[v], d[to]);   // back edge
    else
    {

Aksi takdirde $(v, t o)$ (v, to) bir ağaç kenarıdır. $t o$ köşesinden derinlik öncelikli aramayı başlatıyoruz, onun ebeveyni $v$ olur. Özyinelemeden döndükten sonra $u p [v]$ değerini yeniden hesaplıyoruz.

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

Eğer $u p [t o] \geq d [v]$ up[to] \ge d[v] ise ve $v$ köşesi kök değilse ( $p \neq = - 1$ p \ne -1), o zaman $v$ bir eklem noktasıdır: $t o$ köşesi kökünde olan alt ağaçtan $v$ 'den daha yukarıya çıkılamaz, bu nedenle $v$ 'nin silinmesi bu alt ağacı grafın geri kalanından ayırır.

      if (up[to] \>= d[v] \&\& p != -1) // kök olmayan köşe
        ArtP.insert(v);

$t o$ köşesi, $v$ 'nin gezinti ağacındaki bir sonraki çocuğudur, $c hi l d r e n$ children sayacını artırıyoruz.

      children++;
    }
  }

Gezinti ağacının kökü ( $p = - 1$ p = -1), ancak ve ancak birden fazla çocuğu varsa eklem noktasıdır.

  if (p == -1 \&\& children \> 1)       // DFS ağacının kökü
    ArtP.insert(v);
}

Programın ana kısmı. Girdi verilerini okuyoruz.

scanf("%d %d", &n, &m);
g.resize(n + 1);
for (int i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);

Graf yönsüzdür, bu nedenle her $(a, b)$ kenarını her iki ucunun komşuluk listelerine ekliyoruz.

  g[a].push_back(b);
  g[b].push_back(a);
}

$d$ , $u p$ ve $u se d$ dizileri için bellek ayırıyoruz.

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

Zamanlayıcıyı başlatıyoruz ve henüz ziyaret edilmemiş her köşeden derinlik öncelikli aramayı başlatıyoruz: graf bağlantısız olabilir.

timer = 1;
for (int i = 1; i <= n; i++)
  if (!used[i]) dfs(i);

Eklem noktalarının sayısını, ardından köşelerin kendisini yazdırıyoruz. $A r tP$ kümesi sıralıdır, bu nedenle köşeler artan sırada yazdırılır.

printf("%d\n", ArtP.size());
for (int v : ArtP)
  printf("%d\n", v);

Java Gerçeklemesi

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;
  static int used[], d[], up[];
  static int time;
  static TreeSet<Integer> ArtPoints = new TreeSet<Integer>();
  
  static void dfs (int v, int p)
  {
    int i, to, children;
    used[v] = 1;
    d[v] = up[v] = time++;
    children = 0;
    for (i = 0; i < g[v].size(); i++) 
    {
      to = g[v].get(i);
      if (to == p)  continue;
      if (used[to] == 1)
        up[v] = Math.min(up[v], d[to]);
      else 
      {
        dfs (to, v);
        up[v] = Math.min(up[v], up[to]);
        if ((up[to] >= d[v]) && (p != -1)) ArtPoints.add(v);
        children++;
      }
    }
    if ((p == -1) && (children > 1)) ArtPoints.add(v);
  }

  @SuppressWarnings("unchecked") 
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    g = new ArrayList[n+1]; // unchecked
    used = new int[n+1];
    d = new int[n+1];
    up = new int[n+1];

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();
   
    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g[a].add(b);
      g[b].add(a);
    }
    
    time = 1;
    for(int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i,-1);
    
    System.out.println(ArtPoints.size());
    for(int i : ArtPoints)
      System.out.println(i);
    con.close();
  }
}

Java

Python Gerçeklemesi

Maksimum özyineleme derinliğini artıralım.

import sys
sys.setrecursionlimit(10**6)

Graf, $g$ komşuluk listesi şeklinde saklanır. $u se d$ listesi ziyaret edilmiş köşeleri işaretler, $d$ ve $u p$ listelerinde aynı adlı etiketler saklanır. Bulunan eklem noktaları $A r tP o in t s$ ArtPoints kümesinde toplanır.

g = []
used = []
d = []
up = []
ArtPoints = set()

dfs fonksiyonu, $v$ köşesinden başlayarak derinlik öncelikli arama yapar ve bu arada eklem noktalarını bulur. $p$ parametresi, $v$ köşesinin gezinti ağacındaki ebeveynidir; kök için $p = - 1$ p = -1 olur. $c hi l d r e n$ children değişkeni, $v$ köşesinin gezinti ağacındaki çocuklarını sayar.

def dfs(v, p = -1):
  global t
  children = 0

$v$ köşesine girildiğinde, onu ziyaret edilmiş olarak işaretleriz. $d [v]$ ve $u p [v]$ etiketleri, $t$ 'nin güncel değerini alır, bundan sonra $t$ artırılır.

  used[v] = 1
  d[v] = up[v] = t
  t += 1

$v$ köşesine komşu olan $t o$ köşelerini gözden geçiriyoruz. $(v, t o)$ (v, to) kenarı üç türden biri olabilir:

ters yönde incelenen, ebeveyne giden bir ağaç kenarı ( $t o = p$ to = p). Böyle bir kenarı atlıyoruz;
bir geri kenar ( $t o$ köşesi zaten ziyaret edilmiş ve $t o \neq = p$ to \ne p);
3. henüz ziyaret edilmemiş $t o$ köşesine giden bir ağaç kenarı.

  for to in g[v]:
    if to == p: continue

Eğer $t o$ köşesi zaten ziyaret edilmişse, $(v, t o)$ (v, to) bir geri kenardır. $u p [v]$ değerini yeniden hesaplıyoruz.

    if used[to]:
      up[v] = min(up[v], d[to])
    else:

      dfs(to, v)
      up[v] = min(up[v], up[to])

Eğer $u p [t o] \geq d [v]$ up[to] \ge d[v] ise ve $v$ köşesi kök değilse $(p \neq = - 1)$ (p ≠ -1), o zaman $v$ bir eklem noktasıdır.

      if up[to] >= d[v] and p != -1:
        ArtPoints.add(v)

$t o$ köşesi, $v$ 'nin gezinti ağacındaki bir sonraki çocuğudur, $c hi l d r e n$ children sayacını artırıyoruz.

      children += 1

Gezinti ağacının kökü $(p = - 1)$ (p = -1), ancak ve ancak birden fazla çocuğu varsa eklem noktasıdır.

    if p == -1 and children > 1:
      ArtPoints.add(v)

Programın ana kısmı. Listeleri oluşturuyoruz ve girdi verilerini okuyoruz.

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
used = [0] * (n + 1)
d = [0] * (n + 1)
up = [0] * (n + 1)

Yönsüz grafın kenarlarını okuyoruz ve komşuluk listelerini dolduruyoruz.

for _ in range(m):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Henüz ziyaret edilmemiş her köşeden derinlik öncelikli aramayı başlatıyoruz: graf bağlantısız olabilir.

t = 1
for i in range(1, n + 1):
  if not used[i]: dfs(i)

Eklem noktalarının sayısını, ardından köşelerin kendisini artan sırada yazdırıyoruz.

print(len(ArtPoints))
for x in sorted(ArtPoints):
  print(x)