Bağlılıq (Həll təhlili)

Dərinlik üzrə axtarış vasitəsilə əlaqəli komponentlərin sayını hesablayacağıq. Əgər bu rəqəm $1$ -ə bərabərdirsə, onda qraf əlaqəlidir.

İkinci həll yolu isə qrafda $1$ -ci zirvədən dərinlik üzrə axtarış başlayaraq ziyarət edilən zirvələrin sayını hesablamaqdır. Əgər bu sayı $n$ -ə bərabərdirsə, onda qraf əlaqəlidir.

Misal

Misallarda verilən qraflar belə görünür:

Alqoritmin reallaşdırılması

Əlaqə matrisini $g$ və ziyarət edilmiş zirvələrin massivini $u se d$ elan edək.

#define MAX 101
int g[MAX][MAX], used[MAX];

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarış keçirir.

void dfs(int v)
{
  used[v] = 1;
  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) dfs(i);
}

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

scanf("%d %d", &n, &m);

Massivləri ilkləndiririk.

memset(g,0,sizeof(g)); 
memset(used,0,sizeof(used));

Qrafın əlaqə matrisini qururuq.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Əlaqəlilik komponentlərinin sayı $c n t$ dəyişənində hesablamaq.

cnt = 0;

Əlaqəsiz qraf üzərində dərinlik üzrə axtarış başlayırıq.

for (i = 1; i <= n; i++)
  if (!used[i]) 
  {

dfs funksiyasının çağırış sayı qrafın əlaqəlilik komponentlərinin sayına bərabərdir.

    dfs(i);
    cnt++;
  }

Cavabı çıxarırıq. Əgər qraf yalnız bir əlaqə komponentinə malikdirsə, onda o, əlaqəlidir.

if (cnt == 1) printf("YES\n");
else printf("NO\n");

Alqoritmin reallaşdırılması — ziyarət edilmiş zirvələrin sayı

Əlaqə matrisini $g$ və ziyarət edilmiş zirvələrin massivini $u se d$ elan edək.

#define MAX 101
int g[MAX][MAX], used[MAX];

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarış keçir. $c n t$ dəyişənində ziyarət edilmiş zirvələrin sayını hesablayırıq.

void dfs(int v)
{
  used[v] = 1;
  cnt++;
  for (int i = 1; i <= n; i++)
    if ((g[v][i] == 1) && (used[i] == 0)) dfs(i);
}

C++

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

scanf("%d %d", &n,&m);

Massivləri ilkləndiririk.

memset(g, 0, sizeof(g)); 
memset(used, 0, sizeof(used));

Qrafın əlaqə matrisini qururuq.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

$1$ zirvəsindən dərinlik üzrə axtarış başlayırıq.

cnt = 0;
dfs(1);

Əgər dərinlik üzrə axtarış nəticəsində $n$ ədəd zirvə ziyarət edilmişsə, o zaman qraf əlaqəlidir.

if (cnt == n) printf("YES\n");
else printf("NO\n");

Alqoritmin reallaşdırılması — heç bir kəsişməyən çoxluqlar sistemi

İşçi massivini elan edək.

#define MAX 102
int mas[MAX];

Repr funksiyası $n$ zirvəsini ehtiva edən çoxluğun nümayəndəsi olan zirvənin nömrəsini qaytarır. Nümayəndəni (onun göstəricisi özü üzərində göstərir) tapana qədər növbəti elementin göstəricisi ilə davamedirik.

int Repr(int n)
{
  while (n != mas[n]) n = mas[n];
  return n;
}

Union funksiyası $x$ və $y$ zirvələrini ehtiva edən iki çoxluğu birləşdirir. $x$ və $y$ zirvələrini ehtiva edən çoxluqların nümayəndələrini tapırıq. Bu nümayəndələrin $x_{1}$ x_1 və $y_{1}$ y_1 olmasına icazə verək. Əgər $x_{1} = y_{1}$ x_1 = y_1-dirsə, onda $x$ və $y$ eyni çoxluq içərisində yerləşir və bu halda heç nə etməyə ehtiyac yoxdur. Əks halda, $x_{1}$ x_1 nümayəndəsinin göstəricisini $y_{1}$ y_1-ə yönləndiririk.

void Union(int x, int y)
{
  int x1 = Repr(x), y1 = Repr(y);
  if (x1 == y1) return;
  mas[x1] = y1;
}

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

scanf("%d %d", &n, &m);

İlk əvvəl hər bir zirvə özünü göstəriyir ( $ma s [i] = i$ mas[i] = i).

for (i = 1; i <= n; i++) mas[i] = i;

Qrafın kənarlarını oxuyuruq. Hər bir $a$ və $b$ kənarı üçün $a$ və $b$ zirvələrini ehtiva edən çoxluqları birləşdiririk.

for (i = 1; i <= m; i++)
{
  scanf("%d %d", &a, &b);
  Union(a, b);
}

Əlaqəli komponentlərin sayı $co u n t$ dəyişənində hesablamaq. O, özünü göstəriyən çoxluğu (özünə işarə edən zirvələri) olan zirvələrin sayı bərabərdir.

count = 0;
for (i = 1; i <= n; i++)
  if (mas[i] == i) count++;

Dəyişən $co u n t$ -ın qiymətinə görə cavabı çıxarırıq.

if (count == 1) printf("YES\n");
else printf("NO\n");

Python reallaşdırılması

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarış keçir.

def dfs(v):
  used[v] = 1
  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      dfs(i)

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

n, m = map(int, input().split())

Siyahıları ilkləndiririk.

g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

Qrafın əlaqə matrisini qururuq.

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

Əlaqəlilik komponentlərinin sayı $c n t$ dəyişənində hesablamaq.

cnt = 0

Əlaqəsiz qraf üzərində dərinlik üzrə axtarış başlayırıq.

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

dfs funksiyasının çağırış sayı qrafın əlaqəlilik komponentlərinin sayına bərabərdir.

    dfs(i)
    cnt += 1

Cavabı çıxarırıq. Əgər qraf yalnız bir əlaqə komponentinə malikdirsə, onda o, əlaqəlidir.

if cnt == 1:
  print("YES")
else:
  print("NO")

Python alqoritm reallaşdırması — ziyarət edilmiş zirvələrin sayı

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarış keçir. $c n t$ dəyişənində ziyarət edilmiş zirvələrin sayını hesablayırıq.

def dfs(v):
  used[v] = 1
  global cnt
  cnt += 1
  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      dfs(i)

Python

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

n, m = map(int, input().split())

Siyahıları ilkləndiririk.

g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

Qrafın əlaqə matrisini qururuq.

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

$1$ zirvəsindən dərinlik üzrə axtarış başlayırıq.

cnt = 0
dfs(1)

Əgər dərinlik üzrə axtarış nəticəsində bütün $n$ zirvələr ziyarət edilmişdirsə, o zaman qraf əlaqəlidir.

if cnt == n:
  print("YES")
else:
  print("NO")

Python alqoritm reallaşdırması — heç bir kəsişməyən çoxluqlar sistemi

Repr funksiyası $n$ zirvəsinin daxil olduğu çoxluğun nümayəndəsinin nömrəsini qaytarır. Nümayəndəni (onun göstəriyicisi özü üzərində göstərir) tapana qədər növbəti elementin göstəriyicisi ilə hərəkət edirik.

def Repr(n):
  while n != mas[n]:
    n = mas[n]
  return n

Union funksiyası $x$ və $y$ zirvələrini ehtiva edən iki çoxluğu birləşdirir. $x$ və $y$ zirvələrinin daxil olduğu çoxluqların nümayəndələrini tapırıq. Onların nümayəndələrinin $x_{1}$ x_1 və $y_{1}$ y_1 olmasına icazə verək. Əgər $x_{1} = y_{1}$ x_1 = y_1-dirsə, onda $x$ və $y$ artıq eyni çoxluqda yerləşib, bu halda heç bir şey etmək lazım deyil. Əks halda, $x_{1}$ x_1-in nümayəndə göstəricisini $y_{1}$ y_1-ə yönləndiririk.

def Union(x, y):
  x1 = Repr(x)
  y1 = Repr(y)
  if x1 == y1: return
  mas[x1] = y1

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

n, m = map(int, input().split())

İlk əvvəl hər bir zirvə özünü göstəriyir ( $ma s [i] = i$ mas[i] = i).

mas = [0] * (n + 1)
for i in range(1, n + 1):
  mas[i] = i

Qrafın kənarlarını oxuyuruq. Hər bir $(a, b)$ kənarı üçün $a$ və $b$ zirvələrini ehtiva edən çoxluqları birləşdiririk.

for _ in range(m):
  a, b = map(int, input().split())
  Union(a, b)

Əlaqəli komponentlərin sayı $co u n t$ dəyişənində hesablamaq. Bu, tək özünü göstərən (özünə işarə edən) zirvələrin sayına bərabərdir.

count = 0
for i in range(1, n + 1):
  if mas[i] == i:
    count += 1

Dəyişən $co u n t$ -ın qiymətinə görə cavabı çıxardın.

if count == 1:
  print("YES")
else:
  print("NO")