Зв'язність (Розбір)

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

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

Приклад

Графи, наведені в прикладах, мають вигляд:

Реалізація алгоритму

Оголосимо матрицю суміжності $g$ і масив відвіданих вершин $u se d$ .

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

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

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

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

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

Ініціалізуємо масиви.

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

Будуємо матрицю суміжності графа.

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

Кількість компонент зв'язності підраховуємо у змінній $c n t$ .

cnt = 0;

Запускаємо пошук в глибину на незв'язному графі.

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

Кількість викликів функції dfs дорівнює числу компонент зв'язності графа.

    dfs(i);
    cnt++;
  }

Виводимо відповідь. Якщо граф містить лише одну компоненту зв'язності, то він зв'язний.

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

Реалізація алгоритму — кількість відвіданих вершин

Оголосимо матрицю суміжності $g$ і масив відвіданих вершин $u se d$ .

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

Функція dfs здійснює пошук в глибину з вершини $v$ . У змінній $c n t$ підраховуємо кількість відвіданих вершин.

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++

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

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

Ініціалізуємо масиви.

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

Будуємо матрицю суміжності графа.

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

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

cnt = 0;
dfs(1);

Якщо в результаті пошуку в глибину були відвідані всі $n$ вершин, то граф зв'язний.

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

Реалізація алгоритму — система неперетинних множин

Оголосимо робочий масив.

#define MAX 102
int mas[MAX];

Функція Repr повертає номер вершини — представника множини, що містить вершину $n$ . Рухаємось за вказівником на наступний елемент, поки не зустрінемо представника множини (його вказівник вказує на нього самого).

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

Функція Union об'єднує дві множини, що містять вершини $x$ і $y$ . Знаходимо представників множин, що містять $x$ і $y$ . Нехай цими представниками будуть $x_{1}$ x_1 і $y_{1}$ y_1. Якщо $x_{1} = y_{1}$ x_1 = y_1, то $x$ і $y$ вже знаходяться в одній множині, і в такому разі нічого робити не треба. В іншому випадку вказівник представника $x_{1}$ x_1 перенаправляємо на $y_{1}$ y_1.

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

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

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

Спочатку кожна вершина вказує сама на себе ( $ma s [i] = i$ mas[i] = i).

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

Читаємо ребра графа. Для кожного ребра $(a, b)$ здійснюємо об'єднання множин, що містять вершини $a$ і $b$ .

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

Підраховуємо кількість компонент зв'язності у змінній $co u n t$ . Воно дорівнює кількості вершин – представників множин (які вказують самі на себе).

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

Залежно від значення змінної $co u n t$ виводимо відповідь.

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

Python реалізація

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

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

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

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

Ініціалізуємо списки.

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

Будуємо матрицю суміжності графа.

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

Кількість компонент зв'язності підраховуємо у змінній $c n t$ .

cnt = 0

Запускаємо пошук в глибину на незв'язному графі.

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

Кількість викликів функції dfs дорівнює числу компонент зв'язності графа.

    dfs(i)
    cnt += 1

Виводимо відповідь. Якщо граф містить лише одну компоненту зв'язності, то він зв'язний.

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

Python реалізація алгоритму — кількість відвіданих вершин

Функція dfs здійснює пошук в глибину з вершини $v$ . У змінній $c n t$ підраховуємо кількість відвіданих вершин.

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

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

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

Ініціалізуємо списки.

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

Будуємо матрицю суміжності графа.

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

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

cnt = 0
dfs(1)

Якщо в результаті пошуку в глибину були відвідані всі $n$ вершин, то граф зв'язний.

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

Python реалізація алгоритму — система неперетинних множин

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

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

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

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

Спочатку кожна вершина вказує сама на себе ( $ma s [i] = i$ mas[i] = i).

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

Читаємо ребра графа. Для кожного ребра $(a, b)$ здійснюємо об'єднання множин, що містять вершини $a$ і $b$ .

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

Підраховуємо кількість компонент зв'язності у змінній $co u n t$ . Воно дорівнює кількості вершин — представників множин (які вказують самі на себе).

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

Залежно від значення змінної $co u n t$ виводимо відповідь.

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