Əlaqə komponentləri#2269
Daxil ol

Əlaqə komponentləri (Həll təhlili)

Qrafdakı əlaqəli komponentlərin sayını tapmaq üçün kəsişməz çoxluqlar sistemi (Union-Find) istifadə edilə bilər.

Əvvəlcə hər bir zirvə öz çoxluğuna yerləşdirilir və hər biri onun nümayəndəsidir. Sonra hər bir qırağı üçün və zirvələrini əhatə edən çoxluqlar birləşdirilir. Bütün qıraqlar emal edildikdən sonra əlaqəli komponentlərin sayı sistemdəki çoxluqların sayına bərabərdir.

Bu məsələni başqa bir yolla - dərinlik axtarışı ilə də həll etmək olar. Bu halda dfs prosedurunun başlanğıc sayı qrafın əlaqəli komponentlərinin sayına bərabər olacaq.

Misal

Misalda göstərilən qraf aşağıdakı kimidir:

Əvvəlcə hər bir zirvəni ayrı bir çoxluğa yerləşdiririk, burada o, nümayəndə kimi çıxış edir.

Sonra hər bir qırağı üçün və zirvələrini əhatə edən çoxluqları birləşdiririk. Bütün qıraqlar emal edildikdən sonra iki zirvə eyni əlaqəli komponentə aid olacaq, əgər onların nümayəndəsi eynidirsə.

Əlaqəli komponentlərin sayı kəsişməz çoxluqlar sistemindəki çoxluqların sayına bərabər olur. Bu say çoxluqların nümayəndələrinin sayına əsasən təyin olunur - yəni parent[v] = v şərtini ödəyən zirvələr .

Gösterilen misalda nümayəndələr zirvələr və -dır. Nəticə etibarilə, qrafda üç əlaqəli komponent var.

Alqoritmin realizasiyası

qrafda mümkün maksimum zirvələrin sayını götürür. massivində zirvənin göstərdiyi nömrə qeyd edilir.

#define MAX 102
int mas[MAX];

Repr funksiyası zirvəsinə aid olan çoxluğu təyin edən zirvə-nümayəndəsini qaytarır. Bunun üçün göstəricilər vasitəsilə növbəti eləməntə keçərək çoxluğun nümayəndəsinə qədər gedilir (onun göstəricisi yenə onun özünə işarə edir).

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

Union funksiyası və zirvələrini əhatə edən iki çoxluğu birləşdirir. Əvvəlcə onların nümayəndələri təyin olunur - bunlar x_1 və y_1 olsun. Əgər x_1 = y_1-dırsa, zirvələr artıq eyni çoxluğa aiddir və əlavə tədbirə ehtiyac yoxdur. Əks halda, x_1 nümayəndəsinin göstəricisi y_1-ə yönəldilir.

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. Əvvəlcə hər bir zirvə öz-özünə işarə edir (mas[i] = i).

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

Bitişik matrisini oxuyun. Hər bir qırağı üçün, burada i < j, və zirvələrini əhatə edən çoxluqları birləşdirin.

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

dəyişənində əlaqəli komponentlərin sayını hesablayın. Bu say, öz-özünə işarə edən, yəni çoxluqların nümayəndəsi olan zirvələrin sayına bərabərdir.

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

Cavabı çıxardın.

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

Alqoritmin realizasiyası – dərinlik axtarışı

İşçi massivləri elan edək.

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

dfs funksiyası zirvəsindən başlayaraq qraf boyunca dərinlik axtarışını həyata keçirir.

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

Proqramın əsas hissəsi. Giriş verilənlərini oxuyun.

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

dəyişənində əlaqəli komponentlərin sayını hesablayın.

res = 0;

Bağlı olmayan qrafda dərinlik axtarışı başladın. dfs funksiyası ilə hər başlanğıc hallarında yeni ziyarət olunmayan zirvədən başlayır, beləliklədfs çağırışlarının sayı qrafda əlaqəli komponentlərin sayına bərabərdir.

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

Cavabı çıxardın.

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

Java realizasiyası – 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 realizasiyası – 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 realizasiyası – dsu

Repr funksiyası zirvəsinə aid olan çoxluğu təyin edən zirvə-nümayəndəsini qaytarır. Bunun üçün göstəricilər vasitəsilə növbəti eləməntə keçərək çoxluğun nümayəndəsinə qədər gedilir (onun göstəricisi yenə onun özünə işarə edir).

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

Union funksiyası və zirvələrini əhatə edən iki çoxluğu birləşdirir. Əvvəlcə onların nümayəndələri təyin olunur - bunlar x_1 və y_1 olsun. Əgər x_1 = y_1-dırsa, zirvələr artıq eyni çoxluğa aiddir və əlavə tədbirə ehtiyac yoxdur. Əks halda, x_1 nümayəndəsinin göstəricisi y_1-ə yönəldilir.

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

Proqramın əsas hissəsi. Əvvəlcə hər bir zirvə öz-özünə işarə edir (mas[i] = i).

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

Bitişik matrisini oxuyun. Hər bir qırağı üçün, burada i < j, və zirvələrini əhatə edən çoxluqları birləşdirin.

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)

dəyişənində əlaqəli komponentlərin sayını hesablayın. Bu say, öz-özünə işarə edən, yəni çoxluqların nümayəndəsi olan zirvələrin sayına bərabərdir.

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

Cavabı çıxardın.

print(res)

Python realizasiyası – dfs

dfs funksiyası zirvəsindən başlayaraq qraf boyunca dərinlik axtarışını həyata keçirir.

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

Proqramın əsas hissəsi. Giriş verilənlərini oxuyun.

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

dəyişənində əlaqəli komponentlərin sayını hesablayın.

res = 0

Bağlı olmayan qrafda dərinlik axtarışı başladın. dfs funksiyası ilə hər başlanğıc hallarında yeni ziyarət olunmayan zirvədən başlayır, beləliklədfs çağırışlarının sayı qrafda əlaqəli komponentlərin sayına bərabərdir.

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

Cavabı çıxardın.

print(res)