Ağac? (Həll təhlili)

Qraf $n$ ədəd zirvədən ibarətdir və bir ağacdır əgər və yalnız əgər:

1. Qraf əlaqəlidir. İlk zirvədən dərinlik üzrə axtarışa başlayın. Axtarış zamanı ziyarət olunan zirvələrin sayını sayın. Əgər bu say $n$-ə bərabərdirsə, qraf əlaqəlidir.

2. |V| = |E| + 1. Əgər qraf bir ağacdırsa, o zaman n - 1 kənar ehtiva edir.

3. Qraf dövrə ehtiva etmir. İlk zirvədən dərinlik üzrə axtarışa başlayın. Əgər əks kənar varsa, qraf dövrəyə sahibdir və ağac deyil.

Şərtlər $1)$ və $2)$ və ya $1)$ və $3)$ yerinə yetərli olduqda, qraf ağacdır.

Nümunə

Verilmiş nümunədə göstərilən qraf ağacdır.

Alqoritmin təcəssümü — şərtlərin yoxlanması 1) və 3)

Qrafın qonşuluq matrisi $g$ və massiv $used$ elan edək.

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

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarışı yerinə yetirir. $v$ zirvəsinin əcdadı $p$-dir. Dəyişən $flag$ dövrə tapıldıqda $1$ olur.

void dfs(int v, int p)
{

Əgər qraf artıq ağac deyilsə (flag = 1), axtarışa davam etməyin mənası yoxdur.

  if (flag) return;

$v$ zirvəsini keçilmiş kimi işarələyirik.

  used[v] = 1;

Ziyarət edilən $v$ zirvəsi, $c$ artırılır $1$ vahid.

  c++;

$(v,i)$ kənarı əks kənardır və dövrə yaradır əgər i \ne p və $i$ zirvəsi artıq keçilibsə (used[i] = 1). Dövrə tapıldıqda, flag = 1 təyin edirik. Əgər dövrə yoxdursa, $i$ zirvəsindən axtarışa davam edirik.

  for(int i = 0; i < n; i++)
    if ((i != p) && g[v][i])
      if(used[i]) flag = 1; else dfs(i,v);
}

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

scanf("%d",&n); 
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
  scanf("%d",&g[i][j]);

Dərinlik üzrə axtarış zamanı ziyarət olunan zirvələrin sayı $c$ dəyişənində saxlanılır. Əgər qrafta dövrə yoxdursa, flag = 0 təyin edirik, dövrə tapıldıqda isə $flag$ $1$ olur.

c = 0;
flag = 0;

Bütün zirvələr əvvəlcə keçilməmişdir (massivin $used$ sıfırla dolur).

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

Nol zirvəsindən dərinliyə görə axtarışı başlatırıq. Bu, axtarış ağacının kökü olduğundan valdizi yoxdur. İkinci arqument kimi dfs funksiyasına $-1$ dəyərini veririk.

dfs(0,-1);

Əgər əks kənar varsa (flag = 1) və ya qraf əlaqəli deyilsə (c \ne n), qraf ağac deyildir.

if (flag || (c != n)) printf("NO\n"); else printf("YES\n");

Alqoritmin təcəssümü — şərtlərin yoxlanması 1) və 2)

Qrafın qonşuluq matrisi $g$ və massiv $used$ elan edək.

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

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarışı yerinə yetirir.

void dfs(int v)
{

$v$ zirvəsini keçilmiş kimi işarələyirik.

  used[v] = 1;

Ziyarət edilən $v$ zirvəsi, $c$ artırılır $1$ vahid.

  c++;

$v$ zirvəsindən $i$ zirvəsinə hərəkət edə biləcəyiniz hər bir $i$ zirvəsini seçirik. $v$-dən $i$-yə hərəkət etmək mümkündür, əgər:

1. $(v,i)$ kənarı mövcuddur, yəni g[v][i] = 1;

2. $i$ zirvəsi hələ keçilməmişdir (used[i] = 0)

Əgər hər iki şərt doğrudursa, $i$ zirvəsindən dərinlik üzrə axtarışı davam edirik.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$-i oxuyuruq.

scanf("%d", &n); 

Qraftaki kənarların sayını $Edges$ dəyişənində sayıram.

Edges = 0;

Bütün zirvələr əvvəlcə keçilməmişdir (massivin $used$ sıfırla dolur).

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

Qonşuluq matrisi $g$-i oxuyur və qraftaki kənarların sayını hesablayırıq.

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d", &g[i][j]);
  Edges += g[i][j];
}

Qraftaki $(u,v)$ və $(v,u)$ kənarları eyni sayıldığına görə Edges dəyərini $2$-ə bölürük.

Edges /= 2;

Dərinlik üzrə axtarış zamanı ziyarət olunan zirvələrin sayı dəyişəni $c$-də saxlanılır.

c = 0;

Birinci zirvədən dərinlik üzrə axtarışı başlatırıq.

dfs(1);

Qraf ağacdır əgər kənarların sayı n - 1-ə və o əlaqəlidirsə (c = n).

if ((Edges == n - 1) && (c == n)) printf("YES\n");
else printf("NO\n");

Java təcəssümü

import java.util.*;
//import java.io.*;

public class Main
{
  static int c = 0; 	
  static int m[][], used[];
  
  static void dfs(int v)
  {
    used[v] = 1; c++;
    for(int i = 0; i < m.length; i++) 
      if (m[v][i]== 1 && used[i] == 0) dfs(i);
  }
  
  public static void main(String[] args) //throws IOException
  {
    Scanner con = new Scanner(System.in);
    //Scanner con = new Scanner(new FileReader ("977.in"));
    int n = con.nextInt();
    m = new int[n][n];
    used = new int[n];
    Arrays.fill(used, 0);
    int Edges = 0;
    
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
      m[i][j] = con.nextInt();
      Edges += m[i][j];
    }

    dfs(0); Edges /= 2;

    if ((Edges == n - 1) && (c == n)) 
      System.out.printf("YES"); 
    else 
      System.out.printf("NO");    
  }
}   

Python təcəssümü — şərtlərin yoxlanması 1) və 3)

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarışı yerinə yetirir. $v$ zirvəsinin əcdadı $p$-dir. Dəyişən $flag$ dövrə tapıldıqda $1$ olur.

def dfs(v, p):

Funksiyanı istifadə edən qlobal dəyişənləri elan edək.

  global flag, c

Əgər qraf artıq ağac deyilsə (flag = 1), axtarışa davam etməyin mənası yoxdur.

  if flag: return

$v$ zirvəsini keçilmiş kimi işarələyirik.

  used[v] = 1

Ziyarət edilən $v$ zirvəsi, $c$ artırılır $1$ vahid.

  c += 1

$(v,i)$ kənarı əks kənardır və dövrə yaradır əgər i \ne p və $i$ zirvəsi artıq keçilibsə (used[i] = 1). Dövrə tapıldıqda, flag = 1 təyin edirik. Əgər dövrə yoxdursa, $i$ zirvəsindən axtarışa davam edirik.

  for i in range(n):
    if i != p and g[v][i]:
      if used[i]: flag = 1
      else: dfs(i, v)

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

n = int(input())

Dərinlik üzrə axtarış zamanı ziyarət olunan zirvələrin sayı $c$ dəyişənində saxlanılır. Əgər qrafta dövrə yoxdursa, flag = 0 təyin edirik, dövrə tapıldıqda isə $flag$ $1$ olur.

c = 0
flag = 0

Bütün zirvələr əvvəlcə keçilməmişdir (used siyahısını sıfırlarla doldururuq).

used = [0] * n

Qonşuluq matrisi $g$ yaratırıq, əvvəlcə sıfırlarla doldururuq.

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

Giriş qonşuluq matrisini oxuyuruq.

for i in range(n):
  g[i] = list(map(int, input().split()))

Nol zirvəsindən dərinliyə görə axtarışı başlatırıq.

dfs(0, -1)

Əgər əks kənar varsa (flag = 1) və ya qraf əlaqəli deyilsə (c \ne n), qraf ağac deyildir.

if flag or c != n:
  print("NO")
else:
  print("YES")

Python təcəssümü — şərtlərin yoxlanması 1) və 2)

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarışı yerinə yetirir.

def dfs(v):
  global c

$v$ zirvəsini keçilmiş kimi işarələyirik.

  used[v] = 1

Ziyarət edilən $v$ zirvəsi, $c$ artırılır $1$ vahid.

  c += 1

$v$ zirvəsindən $i$ zirvəsinə hərəkət edə biləcəyiniz hər bir $i$ zirvəsini seçirik. $v$-dən $i$-yə hərəkət etmək mümkündür, əgər:

1. $(v,i)$ kənarı mövcuddur, yəni g[v][i] = 1;

2. $i$ zirvəsi hələ keçilməmişdir (used[i] = 0)

Əgər hər iki şərt doğrudursa, $i$ zirvəsindən dərinlik üzrə axtarışı davam edirik.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$-i oxuyuruq.

n = int(input())

Qraftaki kənarların sayını $Edges$ dəyişənində saxlanılır.

Edges = 0

Bütün zirvələr əvvəlcə keçilməmişdir (used siyahısını sıfırlarla doldururuq).

used = [0] * (n + 1)

Qonşuluq matrisi $g$ yaratırıq, əvvəlcə sıfırlarla doldururuq.

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

Qonşuluq matrisi $g$-i oxuyur və $Edges$ dəyişənində qraftaki kənarların sayını hesablayırıq.

for i in range(1, n + 1):
  g[i] = [0] + list(map(int, input().split()))
  Edges += sum(g[i])

Qraftaki $(u,v)$ və $(v,u)$ kənarları eyni sayıldığına görə Edges dəyərini $2$-ə bölürük.

Edges //= 2

Dərinlik üzrə axtarış zamanı ziyarət olunan zirvələrin sayı dəyişəni $c$-də saxlanılır.

c = 0

Birinci zirvədən dərinlik üzrə axtarışı başlatırıq.

dfs(1)

Qraf ağacdır əgər kənarların sayı n - 1-ə və o əlaqəlidirsə (c = n).

if Edges == n - 1 and c == n:
  print("YES")
else:
  print("NO")