Михаил Гарриевич Делба , 525 группа DungeonMap 8677
Лёвин Александр, 524 группа DungeonMap 8728
n1def build_adj_mat(input_lines):n1def get_adj_matrix(lines):
2    adj_mat = {}2    adj_matrix = {}
3    for line in input_lines:3    for line in lines:
4        cave1, cave2 = line.strip().split()4        cave1, cave2 = line.strip().split()
n5        adj_mat.setdefault(cave1, set()).add(cave2)n5        adj_matrix.setdefault(cave1, set()).add(cave2)
6        adj_mat.setdefault(cave2, set()).add(cave1)6        adj_matrix.setdefault(cave2, set()).add(cave1)
7    return adj_mat7    return adj_matrix
88
n9def can_reach_exit(adj_mat, entrance, exit):n9def can_reach_exit(adj_matrix, ent, exit):
10    adj_caves = set([entrance])10    adj_caves = {ent}
11    fl = True11    flag = True
12    while fl:12    while flag:
13        fl = False13        flag = False
14        for cave1 in list(adj_caves):14        for cave1 in list(adj_caves):
n15            for cave2 in adj_mat.get(cave1, []):n15            for cave2 in adj_matrix.get(cave1, []):
16                if cave2 not in adj_caves:16                if cave2 not in adj_caves:
17                    adj_caves.add(cave2)17                    adj_caves.add(cave2)
n18                    fl = Truen18                    flag = True
19    return exit in adj_caves19    return exit in adj_caves
n20input_lines = []n20lines = []
21while True:21while True:
22    try:22    try:
23        line = input().strip()23        line = input().strip()
24        if not line:24        if not line:
25            break25            break
n26        input_lines.append(line)n26        lines.append(line)
27    except EOFError:27    except EOFError:
28        break28        break
t29entrance = input_lines[-2]t29ent = lines[-2]
30exit = input_lines[-1]30exit = lines[-1]
31adj_mat = build_adj_mat(input_lines[:-2])31adj_mat = get_adj_matrix(lines[:-2])
32if can_reach_exit(adj_mat, entrance, exit):32if can_reach_exit(adj_mat, ent, exit):
33    print('YES')33    print('YES')
34else:34else:
35    print('NO')35    print('NO')
Legends
Colors
 Added 
Changed
Deleted
Links
(f)irst change
(n)ext change
(t)op