Дороги#776

Дороги (Розбір)

Оскільки граф містить $10000$ вершин, для його зберігання будемо використовувати список суміжності. На основі вхідного списку ребер побудуємо відповідне представлення графа. Потім за допомогою пошуку в глибину визначимо кількість компонент зв'язності. Число нових доріг, які необхідно побудувати, буде рівно кількості компонент зв'язності мінус один.

Приклад

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

Граф складається з трьох компонент зв'язності. Щоб об'єднати їх в одну, достатньо додати два ребра.

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

Оголосимо список суміжності $g$ та масив $u se d$ , в якому будемо позначати відвідані вершини.

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

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

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

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

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

Читаємо $m$ ребер, будуємо список суміжності графа.

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

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

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

C++

Виводимо кількість доріг, які необхідно побудувати.

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

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

#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 реалізація

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 реалізація

Збільшимо стек для рекурсії.

import sys
sys.setrecursionlimit(1000000)

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

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

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

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

Читаємо $m$ ребер, будуємо список суміжності графа.

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

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

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

Виводимо кількість доріг, які необхідно побудувати.

print(cnt - 1)