Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313301
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе количество упорядоченных пар различных вершин графа ($A, B$), для которых существует путь из вершины $A$ в вершину $B$.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000, M ≤ 1000; W ≤ 10 000$. Количество строк в файле не превосходит $200$. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
| 100 6 6 1 7 4 1 1 | 12 7 1 7 100 100 100 4 | 1.0 7.0 1.0 5.5 2.0 8.0 12.0 2.5 |
Для приведённого примера из вершины $6$ достижимы $5$ вершин ($7, 1, 4, 100, 12)$, из вершины $1 — 4 (7, 4, 100, 12)$, из вершин $7$ и $4$ — по $2 (100, 12)$, из вершины $100 — 1 (12$), из вершины $12$ — ни одной. Всего $5 + 4 + 2 + 2 + 1 = 14$, поэтому верным ответом будет $14$.
Для каждой вершины $A$ находим множество вершин, достижимых из $A$, обходом в глубину (или в ширину) и складываем размеры этих множеств, не считая саму $A$. Граф маленький — $50$ обходов по $200$ рёбер выполняются мгновенно. Все вершины, включая те, у которых нет исходящих рёбер, должны быть ключами словаря: такая вершина даёт $0$ пар как начало, но должна быть посчитана как конец.
g = {} # вершина -> список соседей
for line in open('23_24.txt'):
s = line.split()
if len(s) < 3:
continue
a, b = int(s[0]), int(s[1]) # веса не нужны
g.setdefault(a, []).append(b)
g.setdefault(b, []) # все вершины — ключи словаря
def reach(start): # вершины, достижимые из start
seen = {start}
stack = [start]
while stack:
v = stack.pop()
for u in g[v]:
if u not in seen:
seen.add(u)
stack.append(u)
return seen
print(sum(len(reach(v)) - 1 for v in g)) # минус сама вершинаВторой способ — множества достижимости рекурсией с запоминанием: достижимые из $v$ — это соседи $v$ и всё, что достижимо из соседей (продолжение после чтения графа):
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
@lru_cache(None)
def R(v): # множество вершин, достижимых из v
s = set()
for u in g[v]:
s.add(u)
s |= R(u) # объединяем с достижимыми из u
return frozenset(s)
print(sum(len(R(v)) for v in g))В графе $50$ вершин; из вершины $1$ достижимы $42$ вершины.
20
