Kəsmə nöqtələri (Həll təhlili)

Oynaq nöqtələri dərinliyinə axtarış vasitəsilə tapılır. Hər bir $v$ təpəsi üçün iki etiket hesablanır:

$d [v]$ — dərinliyinə axtarış zamanı $v$ təpəsinə giriş vaxtı;
$u p [v]$ — $v$ kökündə olan alt ağacdan bir geri qövslə getdikdə çatmaq mümkün olan təpələr arasında minimal giriş vaxtı.

Axtarış ağacının kökü olmayan $v$ təpəsi, dərinliyinə axtarış ağacında $u p [t o] \geq d [v]$ up[to] \ge d[v] bərabərsizliyi ödənən $t o$ oğlu varsa, oynaq nöqtəsidir. Bu bərabərsizlik o deməkdir ki, $t o$ kökündə olan alt ağacdan geri qövslər vasitəsilə $v$ təpəsindən yuxarı qalxmaq mümkün deyil. Buna görə də $v$ silindikdə bu alt ağac qrafın qalan hissəsindən kəsilmiş olacaq.

Axtarış ağacının kökü ancaq və ancaq axtarış ağacında ən azı iki oğlu olduqda oynaq nöqtəsidir.

Misal

Misaldakı qraf aşağıdakı görünüşə malikdir:

Qalın xətlərlə dərinliyinə axtarış ağacının qövsləri qeyd olunub. Hər bir $v$ təpəsinin yanında $d [v] / u p [v]$ d[v] / up[v] etiketləri göstərilib. Oynaq nöqtələri rənglə seçilib.

1-ci təpə — axtarış ağacının köküdür. O, oynaq nöqtəsidir, çünki axtarış ağacında onun iki oğlu var: $2$ və $4$ təpələri.
2-ci təpə — oynaq nöqtəsidir, çünki $(2, 6)$ ağac qövsü üçün $u p [6] \geq d [2] (2 \geq 2)$ up[6] \ge d[2]~(2 \ge 2) ödənilir.
3-cü təpə — oynaq nöqtəsidir, çünki $(3, 8)$ ağac qövsü üçün $u p [8] \geq d [3] (3 \geq 3)$ up[8] \ge d[3]~(3 \ge 3) ödənilir.

Alqoritmin reallaşdırılması

Qraf $g$ qonşuluq siyahısı şəklində saxlanılır. $u se d$ massivi ziyarət edilmiş təpələri qeyd edir, $d$ və $u p$ massivlərində eyniadlı etiketlər saxlanılır. $t im er$ dəyişəni cari dərinliyinə axtarış vaxtını saxlayır. Tapılmış oynaq nöqtələri $A r tP$ çoxluğunda toplanır: bu çoxluq təkrarları istisna edir və təpələri artan sırada saxlayır.

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

dfs funksiyası $v$ təpəsindən dərinliyinə axtarış aparır və eyni zamanda oynaq nöqtələrini tapır. $p$ parametri — $v$ təpəsinin axtarış ağacındakı atasıdır. Ağacın kökü üçün $p = - 1$ p = -1, bu susmaya görə dəyərdir.

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

$v$ təpəsinə girərkən onu ziyarət edilmiş kimi qeyd edirik. $d [v]$ və $u p [v]$ etiketləri taymerin cari dəyərini alır, bundan sonra taymer artırılır.

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

$c hi l d r e n$ children dəyişəni $v$ təpəsinin axtarış ağacındakı oğullarını sayır; bu rəqəm $v$ kök olduqda lazım olacaq.

  int children = 0;

$v$ ilə qonşu olan $t o$ təpələrini gəzirik. $(v, t o)$ (v, to) qövsü üç növdən biri ola bilər:

geriyə istiqamətdə baxılan ağac qövsü, ataya ( $t o = p$ to = p). Belə qövsü atlayırıq;
geri qövs (təpə $t o$ artıq ziyarət edilib və $t o \neq = p$ to \ne p);
hələ ziyarət edilməmiş $t o$ təpəsinə aparan ağac qövsü.

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

Əgər $t o$ təpəsi artıq ziyarət edilibsə, onda $(v, t o)$ (v, to) — geri qövsdür. $u p [v]$ dəyərini yenidən hesablayırıq.

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

Əks halda $(v, t o)$ (v, to) — ağac qövsüdür. $t o$ təpəsindən dərinliyinə axtarış başladırıq, onun atası $v$ olur. Rekursiyadan qayıtdıqdan sonra $u p [v]$ dəyərini yenidən hesablayırıq.

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

Əgər $u p [t o] \geq d [v]$ up[to] \ge d[v] və $v$ təpəsi kök deyilsə ( $p \neq = - 1$ p \ne -1), onda $v$ — oynaq nöqtəsidir: $t o$ kökündə olan alt ağacdan $v$ -dən yuxarı qalxmaq mümkün deyil, buna görə $v$ -nin silinməsi bu alt ağacı qrafın qalan hissəsindən kəsəcək.

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

$t o$ təpəsi — axtarış ağacında $v$ -nin növbəti oğludur, $c hi l d r e n$ children sayğacını artırırıq.

      children++;
    }
  }

Axtarış ağacının kökü ( $p = - 1$ p = -1) ancaq və ancaq onun birdən çox oğlu olduqda oynaq nöqtəsidir.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Qraf istiqamətsizdir, buna görə hər $(a, b)$ qövsünü onun hər iki ucunun qonşuluq siyahısına əlavə edirik.

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

$d$ , $u p$ və $u se d$ massivləri üçün yaddaş ayırırıq.

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

Taymeri ilkinləşdiririk və hələ ziyarət edilməmiş hər bir təpədən dərinliyinə axtarış başladırıq: qraf əlaqəli olmaya bilər.

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

Oynaq nöqtələrinin sayını, sonra isə təpələrin özlərini çap edirik. $A r tP$ çoxluğu sıralanmışdır, buna görə təpələr artan sırada çap olunur.

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

Java reallaşdırılması

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 reallaşdırılması

Maksimal rekursiya dərinliyini artıraq.

import sys
sys.setrecursionlimit(10**6)

Qraf $g$ qonşuluq siyahısı şəklində saxlanılır. $u se d$ siyahısı ziyarət edilmiş təpələri qeyd edir, $d$ və $u p$ siyahılarında eyniadlı etiketlər saxlanılır. Tapılmış oynaq nöqtələri $A r tP o in t s$ ArtPoints çoxluğunda toplanır.

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

dfs funksiyası $v$ təpəsindən dərinliyinə axtarış aparır və eyni zamanda oynaq nöqtələrini tapır. $p$ parametri — $v$ təpəsinin axtarış ağacındakı atasıdır; kök üçün $p = - 1$ p = -1. $c hi l d r e n$ children dəyişəni $v$ təpəsinin axtarış ağacındakı oğullarını sayır.

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

$v$ təpəsinə girərkən onu ziyarət edilmiş kimi qeyd edirik. $d [v]$ və $u p [v]$ etiketləri $t$ -nin cari dəyərini alır, bundan sonra $t$ artırılır.

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

$v$ ilə qonşu olan $t o$ təpələrini gəzirik. $(v, t o)$ (v, to) qövsü üç növdən biri ola bilər:

geriyə istiqamətdə baxılan ağac qövsü, ataya ( $t o = p$ to = p). Belə qövsü atlayırıq;
geri qövs (təpə $t o$ artıq ziyarət edilib və $t o \neq = p$ to \ne p);
hələ ziyarət edilməmiş $t o$ təpəsinə aparan ağac qövsü.

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

Əgər $t o$ təpəsi artıq ziyarət edilibsə, onda $(v, t o)$ (v, to) — geri qövsdür. $u p [v]$ dəyərini yenidən hesablayırıq.

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

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

Əgər $u p [t o] \geq d [v]$ up[to] \ge d[v] və $v$ təpəsi kök deyilsə $(p \neq = - 1)$ (p ≠ -1), onda $v$ — oynaq nöqtəsidir.

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

$t o$ təpəsi — axtarış ağacında $v$ -nin növbəti oğludur, $c hi l d r e n$ children sayğacını artırırıq.

      children += 1

Axtarış ağacının kökü $(p = - 1)$ (p = -1) ancaq və ancaq onun birdən çox oğlu olduqda oynaq nöqtəsidir.

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

Proqramın əsas hissəsi. Siyahıları yaradırıq və giriş məlumatlarını oxuyuruq.

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

İstiqamətsiz qrafın qövslərini oxuyuruq və qonşuluq siyahılarını doldururuq.

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

Hələ ziyarət edilməmiş hər bir təpədən dərinliyinə axtarış başladırıq: qraf əlaqəli olmaya bilər.

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

Oynaq nöqtələrinin sayını, sonra isə təpələrin özlərini artan sırada çap edirik.

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