Проверьте, образуют ли данные круги один компонент

Дан двумерный массив A[][] размера N×3, где каждый элемент массива состоит из {x, y, r}, где x и y — координаты этой окружности, а r — радиус этой окружности. , задача состоит в том, чтобы убедиться, что все окружности образуют единую компоненту, где компонентом является множество связанных окружностей.

Примечание: Две окружности соединены, если они касаются или пересекаются друг с другом.

Примеры:

Input: A[][] = {{0, 0, 2}, {0, 3, 3}, {0, 6, 1}, {1, 0, 1}}
Output: true
Explanation: All circles are connected to every other circle.

Input: A[][] = {{0, 0, 1}, {0, 3, 1}, {0, 4, 1}, {1, 0, 1}}
Output: false
Explanation: Circles at index 0 and 3 form a single component 
while circle 1 and 2 form separate component. 
Since there are multiple components, the output is false. 

Подход: Решение проблемы может быть получено с использованием следующей идеи.

The idea is to construct a graph from the given input and check if corresponding vertices touch or intersect each other and in the end find that the graph forms a single connected component or not [i.e. if all the vertices can be visited starting from any vertex].

Ниже приведены шаги для реализации вышеуказанного подхода:

• Для каждого круга в A найдите расстояние между их центрами.
  • Если расстояние <= сумма радиусов
    • соедините обе вершины, представляющие эти круги
• Выполните поиск в глубину из одного узла на графике.
• Теперь проверьте посещаемый массив
  • Если есть непосещенная вершина, вернуть false .
• Возвращает true, если непосещенной вершины нет.

Ниже приведена реализация кода вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N ² )