Условие
На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам B и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Решение
from itertools import permutations
graph_edges = [
('A','E'), ('A','C'), ('A','F'),
('B','H'), ('B','F'),
('C','G'), ('C','F'),
('D','E'), ('D','H'),
('G','H')
]
table_edges = [
(1,3), (1,4), (1,6),
(2,4), (2,7),
(3,8),
(5,6), (5,7), (5,8),
(7,8)
]
vertices = ['A','B','C','D','E','F','G','H']
nums = [1,2,3,4,5,6,7,8]
table_set = {frozenset(e) for e in table_edges}
results = set()
for perm in permutations(nums):
mapping = dict(zip(vertices, perm))
mapped = {frozenset((mapping[a], mapping[b])) for a,b in graph_edges}
if mapped == table_set:
results.add(mapping['B'])
results.add(mapping['G'])
print(''.join(str(x) for x in sorted(results)))Ответ:36
