Yollar#776

Yollar (Həll təhlili)

Grafda $10000$ təpə olduğu üçün onun saxlanması üçün qonşuluq siyahısından istifadə edəcəyik. Verilən kənar siyahısına əsasən qrafın müvafiq təsvirini quracağıq. Sonra dərinə axtarışla bağlılıq komponentlərinin sayını təyin edəcəyik. Tikilməli olan yeni yolların sayı bağlılıq komponentlərinin sayından bir az olacaqdır.

Nümunə

Nümunədə verilən qrafın görünüşü belədir:

Qraf üç bağlılıq komponentindən ibarətdir. Onları birləşdirmək üçün iki qılınc əlavə etmək kifayətdir.

Alqoritmin həyata keçirilməsi

Qonşuluq siyahısı $g$ və ziyarət edilən təpələri qeyd edəcəyimiz $u se d$ massivini elan edək.

vector<vector<int> > g;
vector<int> used;

dfs funksiyası təpə $v$ -dən başlayaraq dərinə axtarışı həyata keçirir.

void dfs(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs(to);
}

Proqramın əsas hissəsi. Daxil edilmə məlumatlarını oxuyuruq.

scanf("%d %d", &n, &m);
g.resize(n + 1);

$m$ kənarını oxuyuq, qrafın qonşuluq siyahısını qururuq.

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

Giriş qrafda dərinə axtarış həyata keçiririk. $c n t$ dəyişənində bağlılıq komponentlərinin sayını sayırıq.

used.resize(n + 1);
cnt = 0;
for (i = 1; i <= n; i++)
  if (used[i] == 0)
  {
    dfs(i);
    cnt++;
  }

C++

Tikilməsi lazım olan yolların sayını çıxarırıq.

printf("%d\n", cnt - 1);

Alqoritmin həyata keçirilməsi — birləşməyən cütlük sistemi

#include <stdio.h>
#define MAX 10001

int mas[MAX];

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

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

int a, b, i, j, n, m, count;

int main(void)
{
  scanf("%d %d", &n, &m);
  for (i = 1; i <= n; i++) mas[i] = i;
  for (i = 0; i < m; i++)
  {
    scanf("%d %d", &a, &b);
    Union(a, b);
  }

  count = 0;
  for (i = 1; i <= n; i++)
    if (mas[i] == i) count++;
  printf("%d\n", count - 1);
  return 0;
}

C++

Java həyata keçirilməsi

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;	
  static boolean used[];
  static int n, m;
  
  static void dfs(int v)
  {
    used[v] = true;
    for(int i = 0; i < g[v].size(); i++)
    {
      int to = g[v].get(i);
      if (used[to] == false) dfs(to);
    }
  }
  
  @SuppressWarnings("unchecked")
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    
    used = new boolean[n+1];
    g = new ArrayList[n+1];
    for(int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();      
      g[a].add(b);
      g[b].add(a);
    }
    
    int cnt = 0;
    for(int i = 1; i <= n; i++)
      if (used[i] == false)
      {
        dfs(i);
        cnt++;
      }

    System.out.println(cnt - 1);
    con.close();
  }
}

Java

Python həyata keçirilməsi

Rekursiya üçün yığını artıracağıq.

import sys
sys.setrecursionlimit(1000000)

dfs funksiyası təpə $v$ -dən başlayaraq dərinə axtarışı həyata keçirir.

def dfs(v):
  used[v] = 1
  for to in g[v]:
    if not used[to]:
      dfs(to)

Proqramın əsas hissəsi. Daxil edilmə məlumatlarını oxuyuruq.

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
used = [0] * (n + 1)

$m$ kənarını oxuyuq, qrafın qonşuluq siyahısını qururuq.

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

Giriş qrafda dərinə axtarış həyata keçiririk. $c n t$ dəyişənində bağlılıq komponentlərinin sayını sayırıq.

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

Tikilməsi lazım olan yolların sayını çıxarırıq.

print(cnt - 1)