Как найти подключенные компоненты в массиве - PullRequest
Новая
       21

Как найти подключенные компоненты в массиве

0 голосов
/ 04 ноября 2018

Я пытаюсь решить проблему с алгоритмом в хакерранке, Дороги и библиотеки . Суть проблемы заключается в использовании DFS для поиска подключенных компонентов (CC) с помощью массива.

Вот тестовый пример: 

queries = [
  {
    n_cities_roads: [9,2],
    c_lib_road: [91, 84],
    matrix: [
      [8, 2], [2, 9]
    ]
  },
  {
    n_cities_roads: [5,9],
    c_lib_road: [92, 23],
    matrix: [
      [2,1], [5, 3], [5,1], 
      [3,4], [3,1],  [5, 4], 
      [4,1], [5,2],  [4,2]
    ]
  },
  {
    n_cities_roads: [8,3],
    c_lib_road: [10, 55],
    matrix: [
      [6,4], [3,2], [7,1]
    ]
  },
  {
    n_cities_roads: [1, 0],
    c_lib_road: [5, 3],
    matrix: []
  },

  {
    n_cities_roads: [2, 0],
    c_lib_road: [102, 1],
    matrix: []
  }
]

queries.each do |query|
  (n_city, n_road), (c_lib, c_road) = [*query[:n_cities_roads]], [*query[:c_lib_road]]
  roads_and_libraries n_city, c_lib, c_road, query[:matrix]
end

Вывод должен быть: 

805
184
80
5
204

Мое текущее решение ниже может получить CC для некоторых случаев, но не для всех. 

def dfs(i, visited, matrix)
  visited[i] = true
  unless matrix[i].nil?
    matrix[i].each do |j|
      unless visited[j]
        dfs j, visited, matrix
      end
    end
  end
end

def roads_and_libraries(no_cities, c_lib, c_road, cities)
  return c_lib * no_cities if c_lib <= c_road
  visited, count = Array.new(no_cities, false), 0

  (0..no_cities).each do |i|
    unless visited[i]
      count += 1
      dfs i, visited, cities
    end
  end
  p (c_road * (no_cities - count)) + (c_lib * count)
end

Результат теста с моим кодом выше: 

805
184
7
305

Я пытаюсь понять, как правильно использовать DFS для поиска подключенных компонентов. Не уверен, где я иду не так.

1 Ответ

0 голосов
/ 04 ноября 2018

Просто напечатайте эту строку: 

p roads_and_libraries n_city, c_lib, c_road, query[:matrix]

Не это 

p (c_road * (no_cities - count)) + (c_lib * count)

Поскольку в методе есть возврат: 

return c_lib * no_cities if c_lib <= c_road

Я не знаю алгоритм, но кажется, что матрица не может быть пустой [], по крайней мере, она должна быть [[1,1]], чтобы получить требуемый вывод: 

roads_and_libraries 1, 5, 3, [[1,1]] #=> 5
roads_and_libraries 2, 102, 1, [[1,1]] #=> 204

Итак, чтобы иметь дело с пустой матрицей, можно добавить это как первую строку в методе dfs: 

matrix = [[1,1]] if matrix.empty?
...