Независимость городов

@golz29 · Регистрация: 05.09.2022

Студворк — интернет-сервис помощи студентам

На острове расположены несколько государств, изолированных друг от друга. У программиста Васи есть данные обо всех дорогах острова, заданные в виде весовой матрицы соответствующего графа, узлы которого – города, а веса рёбер – расстояния между ними. Напишите программу, которая определяет, сколько государств находится на острове.

Входные данные
В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог.

Выходные данные
Программа должна вывести одно число – количество отдельных государств на карте острова.

Примеры
входные данные
5
0 6 3 0 0
6 0 8 0 0
3 8 0 0 0
0 0 0 0 7
0 0 0 7 0
выходные данные
2

@Parramon · 07.11.2022, 13:14

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def dfs(v):
    visited[v] = True
    for w in adj_list[v]:
        if visited[w] == False:  # посещён ли текущий сосед?
            dfs(w)
n = 5
city_list = [[0, 6, 3, 0, 0,],
            [6, 0, 8, 0, 0],
            [3, 8, 0, 0, 0],
            [0, 0, 0, 0, 7],
            [0, 0, 0, 7, 0]]
adj_list = []
for x in city_list:
    t = []
    for i in range(len(x)):
        if x[i] != 0:
            t.append(i)
    adj_list.append(t)
visited = [False] * n  # массив "посещена ли вершина?"
res = 0
for v in range(n):
    if not visited[v]:
        res += 1
        dfs(v)
print(res)

Новые блоги и статьи Все статьи Все блоги /
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .

@golz29 1 / 1 / 0 Регистрация: 05.09.2022 Сообщений: 56

	Независимость городов 07.11.2022, 10:39. Показов 672. Ответов 1 Метки python, python 3.9, питон (Все метки) На острове расположены несколько государств, изолированных друг от друга. У программиста Васи есть данные обо всех дорогах острова, заданные в виде весовой матрицы соответствующего графа, узлы которого – города, а веса рёбер – расстояния между ними. Напишите программу, которая определяет, сколько государств находится на острове. Входные данные В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог. Выходные данные Программа должна вывести одно число – количество отдельных государств на карте острова. Примеры входные данные 5 0 6 3 0 0 6 0 8 0 0 3 8 0 0 0 0 0 0 0 7 0 0 0 7 0 выходные данные 2 0