Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313145
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе количество вершин графа, лежащих хотя бы на одном пути из вершины с номером $1$ в вершину с номером $100$ (сами вершины $1$ и $100$ также учитываются). Существование хотя бы одного такого пути гарантируется.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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 |
Для приведённого примера на путях из вершины $1$ в вершину $100$ лежат вершины $1, 7, 4$ и $100$, а вершины $6$ и $12$ не лежат ни на одном таком пути, поэтому верным ответом будет $4$.
Вершина лежит на каком-нибудь пути из $1$ в $100$ тогда и только тогда, когда она достижима из $1$ и из неё достижима вершина $100$. Первое множество даёт обход прямого графа из вершины $1$, второе — обход обратного графа из вершины $100$; ответ — размер пересечения. Веса не нужны; ацикличность гарантирует, что путь «$1 → v$» и путь «$v → 100$» не пересекаются и склеиваются в один путь.
g = {} # прямой граф
r = {} # обратный граф
for line in open('23_14.txt'):
s = line.split()
if len(s) < 3:
continue
a, b = int(s[0]), int(s[1]) # веса не нужны
g.setdefault(a, []).append(b)
r.setdefault(b, []).append(a)
def reach(adj, start): # вершины, достижимые из start по adj
seen = {start}
stack = [start]
while stack:
v = stack.pop()
for u in adj.get(v, []):
if u not in seen:
seen.add(u)
stack.append(u)
return seen
print(len(reach(g, 1) & reach(r, 100))) # достижимы из 1 И ведут в 100Второй способ — через счётчики путей из предыдущих заданий: $v$ лежит на пути, если число путей $1 → v$ и число путей $v → 100$ оба положительны. Продолжение программы после чтения графа:
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
def cnt(src, dst): # число путей src -> dst
@lru_cache(None)
def f(v):
if v == dst:
return 1
return sum(f(u) for u in g.get(v, []))
return f(src)
verts = set(g) | set(r)
print(sum(1 for v in verts if cnt(1, v) > 0 and cnt(v, 100) > 0))Из вершины $1$ достижимы $46$ вершин, в вершину $100$ ведут пути из $44$ вершин, и та и другая достижимость есть у $40$ вершин (включая $1$ и $100$); всего в графе $50$ вершин.
20
