Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for How to Find Friends by vtflnk
from collections import deque
def check_connection(network: tuple[str], name1: str, name2: str) -> bool:
# Построим граф в виде словаря смежности
graph = {}
for connection in network:
node1, node2 = connection.split('-')
if node1 not in graph:
graph[node1] = []
if node2 not in graph:
graph[node2] = []
graph[node1].append(node2)
graph[node2].append(node1)
# Используем очередь для реализации BFS
queue = deque([name1])
visited = set()
while queue:
current = queue.popleft()
if current == name2:
return True
if current not in visited:
visited.add(current)
# Добавляем всех соседей текущего узла в очередь
queue.extend(graph[current])
return False
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"scout2", "scout3") == True, "Scout Brotherhood"
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"super", "scout2") == True, "Super Scout"
assert check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"dr101", "sscout") == False, "I don't know any scouts."
Aug. 26, 2024
Comments:
