Дерево? (Розбір)

Граф з $n$ вершин є деревом тоді і тільки тоді, коли:

1. Граф зв'язний. Запустимо пошук в глибину з першої вершини. Підрахуємо кількість відвіданих вершин в процесі пошуку. Якщо воно дорівнює $n$, то граф є зв'язним.

2. |V| = |E| + 1. Якщо граф є деревом, то він містить n - 1 ребро.

3. Граф не містить циклів. Запустимо пошук в глибину з першої вершини. Якщо існує зворотне ребро, то граф має цикл і не є деревом.

Виконання умов $1)$ і $2)$ або $1)$ і $3)$ достатньо для того, щоб граф був деревом.

Приклад

Граф, наведений у прикладі, є деревом.

Реалізація алгоритму — перевірка умов 1) і 3)

Оголосимо матрицю суміжності графа $g$ та масив $used$.

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

Функція dfs реалізує пошук в глибину з вершини $v$. Предком вершини $v$ є $p$. Змінна $flag$ стане рівною $1$, якщо буде виявлено цикл.

void dfs(int v, int p)
{

Якщо граф вже не є деревом (flag = 1), то немає сенсу продовжувати пошук.

  if (flag) return;

Позначаємо вершину $v$ як пройдену.

  used[v] = 1;

Відвідана вершина $v$, збільшуємо $c$ на $1$.

  c++;

Ребро $(v,i)$ буде зворотним і утворюватиме цикл, якщо i \ne p і при цьому вершина $i$ вже була пройдена (used[i] = 1). У разі виявлення циклу встановимо flag = 1. Якщо циклу немає, то продовжуємо пошук з вершини $i$.

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

Основна частина програми. Читаємо вхідні дані.

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

У змінній $c$ підраховуємо кількість відвіданих вершин при пошуку в глибину. Встановимо flag = 0, якщо в графі немає циклу. При виявленні циклу $flag$ стане рівним $1$.

c = 0;
flag = 0;

Усі вершини спочатку є непройденими (обнуляємо масив $used$).

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

Запускаємо пошук в глибину з нульової вершини. Оскільки вона є коренем дерева пошуку, то не має батька. Як другий аргумент передаємо функції dfs значення $-1$.

dfs(0,-1);

Граф не буде деревом, якщо існує зворотне ребро (flag = 1) або граф не є зв'язним (c \ne n).

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

Реалізація алгоритму — перевірка умов 1) і 2)

Оголосимо матрицю суміжності графа $g$ та масив $used$.

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

Функція dfs реалізує пошук в глибину з вершини $v$.

void dfs(int v)
{

Позначаємо вершину $v$ як пройдену.

  used[v] = 1;

Відвідана вершина $v$, збільшуємо $c$ на $1$.

  c++;

Перебираємо вершини $i$, куди можна рухатись з $v$. Переміщення з $v$ в $i$ можливе, якщо:

1. існує ребро $(v,i)$, тобто g[v][i] = 1;

2. вершина $i$ ще не пройдена (used[i] = 0)

Якщо обидві умови справджуються, то продовжуємо пошук в глибину з вершини $i$.

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

Основна частина програми. Читаємо вхідне значення $n$.

scanf("%d", &n); 

Кількість ребер у графі підраховуємо в змінній $Edges$.

Edges = 0;

Усі вершини спочатку є непройденими (обнуляємо масив $used$).

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

Читаємо матрицю суміжності $g$. Підраховуємо кількість ребер у графі.

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

Оскільки граф неорієнтований, то ребра $(u,v)$ та $(v,u)$ вважаються однаковими. Поділимо значення $Edges$ на $2$.

Edges /= 2;

У змінній $c$ підраховуємо кількість відвіданих вершин при пошуку в глибину.

c = 0;

Запускаємо пошук в глибину з вершини $1$.

dfs(1);

Граф є деревом, якщо кількість ребер у ньому дорівнює n - 1, а також якщо він зв'язний (c = n).

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

Java реалізація

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 реалізація — перевірка умов 1) і 3)

Функція dfs реалізує пошук в глибину з вершини $v$. Предком вершини $v$ є $p$. Змінна $flag$ стане рівною $1$, якщо буде виявлено цикл.

def dfs(v, p):

Оголосимо глобальні змінні, що використовуються функцією.

  global flag, c

Якщо граф вже не є деревом (flag = 1), то немає сенсу продовжувати пошук.

  if flag: return

Позначаємо вершину $v$ як пройдену.

  used[v] = 1

Відвідана вершина $v$, збільшуємо $c$ на $1$.

  c += 1

Ребро $(v,i)$ буде зворотним і утворюватиме цикл, якщо i \ne p і при цьому вершина $i$ вже була пройдена (used[i] = 1). У разі виявлення циклу встановимо flag = 1. Якщо циклу немає, то продовжуємо пошук з вершини $i$.

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

Основна частина програми. Читаємо вхідне значення $n$.

n = int(input())

У змінній $c$ підраховуємо кількість відвіданих вершин при пошуку в глибину. Встановимо flag = 0, якщо в графі немає циклу. При виявленні циклу $flag$ стане рівним $1$.

c = 0
flag = 0

Усі вершини спочатку є непройденими (список $used$ заповнюємо нулями).

used = [0] * n

Створимо матрицю суміжності $g$, спочатку заповнюємо її нулями.

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

Читаємо вхідну матрицю суміжності.

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

Запускаємо пошук в глибину з вершини $0$.

dfs(0, -1)

Граф не буде деревом, якщо існує зворотне ребро (flag = 1) або граф не є зв'язним (c \ne n).

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

Python реалізація — перевірка умов 1) і 2)

Функція dfs реалізує пошук в глибину з вершини $v$.

def dfs(v):
  global c

Позначаємо вершину $v$ як пройдену.

  used[v] = 1

Відвідана вершина $v$, збільшуємо $c$ на $1$.

  c += 1

Перебираємо вершини $i$, куди можна рухатись з $v$. Переміщення з $v$ в $i$ можливе, якщо:

1. існує ребро $(v,i)$, тобто g[v][i] = 1;

2. вершина $i$ ще не пройдена (used[i] = 0)

Якщо обидві умови справджуються, то продовжуємо пошук в глибину з вершини $i$.

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

Основна частина програми. Читаємо вхідне значення $n$.

n = int(input())

Кількість ребер у графі підраховуємо в змінній $Edges$.

Edges = 0

Усі вершини спочатку є непройденими (список $used$ заповнюємо нулями).

used = [0] * (n + 1)

Створимо матрицю суміжності $g$, спочатку заповнюємо її нулями.

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

Читаємо матрицю суміжності $g$. У змінній $Edges$ підраховуємо кількість ребер у графі.

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

Оскільки граф неорієнтований, то ребра $(u,v)$ та $(v,u)$ вважаються однаковими. Поділимо значення $Edges$ на $2$.

Edges //= 2

У змінній $c$ підраховуємо кількість відвіданих вершин при пошуку в глибину.

c = 0

Запускаємо пошук в глибину з вершини $1$.

dfs(1)

Граф є деревом, якщо кількість ребер у ньому дорівнює n - 1, а також якщо він зв'язний (c = n).

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