Компоненти зв'язності (Розбір)

Для знаходження кількості компонент зв'язності в графі можна використовувати систему неперетинних множин (Union-Find).

Спочатку кожна вершина розміщується в власну множину, і кожна з них є її представником. Потім для кожного ребра $(u, v)$ об'єднуються множини, що містять вершини $u$ і $v$ . Після обробки всіх ребер число компонент зв'язності дорівнює кількості множин в системі.

Цю задачу можна вирішити іншим способом — за допомогою пошуку в глибину. У цьому випадку кількість запусків процедури dfs співпадатиме з числом компонент зв'язності графа.

Приклад

Граф, наведений у прикладі, має такий вигляд:

Спочатку кожну вершину поміщаємо в окрему множину, де вона виступає представником.

Потім для кожного ребра $(u, v)$ об'єднуємо множини, що містять вершини $u$ і $v$ . Після обробки всіх ребер дві вершини належатимуть одній компоненті зв'язності, якщо у них співпадає представник.

Кількість компонент зв'язності збігається з числом множин у системі неперетинних множин. Це число визначається кількістю представників — тих вершин $v$ , для яких виконується умова $p a r e n t [v] = v$ parent[v] = v.

У наведеному прикладі представниками є вершини $3, 5$ і $6$ . Отже, граф містить три компоненти зв'язності.

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

$M A X$ зберігає максимальну кількість вершин в графі. У масиві $ma s [i]$ записаний номер вершини, на яку вказує вершина $i$ .

#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_{1}$ x_1 та $y_{1}$ y_1. Якщо $x_{1} = y_{1}$ x_1 = y_1, то вершини вже належать одній множині і додаткових дій не потрібно. В іншому випадку вказівник представника $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;
}

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

scanf("%d",&n);
for (i = 1; i <= n; i++) mas[i] = i;

Читаємо матрицю суміжності. Для кожного ребра $(i, j)$ , де $i < j$ i < j, виконуємо об'єднання множин, що містять вершини $i$ і $j$ .

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d",&value);
  if (i > j) continue;
  if (value) Union(i,j);
}

C++

У змінній $co u n t$ підраховуємо кількість компонент зв'язності. Це число співпадає з кількістю вершин-представників множин, тобто тих, які вказують самі на себе.

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

Виводимо відповідь.

printf("%d\n",count);

Реалізація алгоритму – пошук в глибину

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

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

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

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

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

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

У змінній $r es$ підраховуємо кількість компонент зв'язності.

res = 0;

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

memset(used,0,sizeof(used));
for (i = 0; i < n; i++)
  if (!used[i])
  {
    dfs(i);
    res++;
  }

C++

Виводимо відповідь.

printf("%d\n",res);

Java реалізація – dfs

import java.util.*;

public class Main
{
  static int g[][], used[];
  static int n;
  
  static void dfs(int v)
  {
    used[v] = 1;
    for(int i = 1; i <= n; i++) 
      if (g[v][i] == 1 && used[i] == 0) dfs(i);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new int[n+1][n+1];
    used = new int[n+1];
    
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      g[i][j] = con.nextInt();;

    int res = 0;
    for(int i = 1; i <= n; i++)
      if (used[i] == 0)
      {
        dfs(i);
        res++;
      }

    System.out.println(res);
    con.close();
  }
}

Java

Java реалізація – dsu

import java.util.*;

public class Main
{
  static int mas[];
  static int n;
  
  static int Repr(int n)
  {
    while (n != mas[n]) n = mas[n];
    return n;  
  }

  static void Union(int x,int y)
  {
    int x1 = Repr(x);
    int y1 = Repr(y);
    if (x1 == y1) return;
    mas[x1] = y1;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    mas = new int[n+1];
    for(int i = 1; i <= n; i++) mas[i] = i;
    
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    {
      int val = con.nextInt();
      if (i > j) continue;
      if (val == 1) Union(i,j);
    }
    
    int count = 0;
    for(int i = 1; i <= n; i++)
      if (mas[i] == i) count++;

    System.out.println(count);
    con.close();
  }
}

Java

Python реалізація – dsu

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

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

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

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

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

n = int(input())
mas = [int(i) for i in range (n + 1)]

for i in range(1,n + 1):
  lst = [0] + [int(j) for j in input().split()]
  for j in range(1, n + 1):
    if (i < j and lst[j] == 1): Union(i, j)

У змінній $r es$ підраховуємо кількість компонент зв'язності. Це число співпадає з кількістю вершин-представників множин, тобто тих, які вказують самі на себе.

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

Виводимо відповідь.

print(res)

Python реалізація – dfs

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

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

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

n = int(input())
g = [[0] * n for _ in range(n)]
used = [0] * n
for i in range(n):
  row = list(map(int, input().split()))
  for j in range(n):
    g[i][j] = row[j]

Python

У змінній $r es$ підраховуємо кількість компонент зв'язності.

res = 0

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

Виводимо відповідь.

print(res)