Задачи про графы

Здесь предложено несколько задач про обработку графов.

Договорённости

Граф хранится в словаре словарей таким образом, что если такой словарь связан с переменной graph, то graph[x][y] — это количество рёбер от вершины x до вершины y.

Программа должна считывать граф, поданный в следующем формате: в первой строчке — количество рёбер \(N\), в каждой из \(N\) следующих — по паре чисел (начало и конец ребра). Считается, что множество вершин графа — все целые неотрицательные числа.

Вся дополнительная информация подаётся после графа.

Задания

  1. Применить print к внутреннему представлению заданного графа.

Пример:

-- ВХОД --
5
0 1
1 0
0 1
5 6
7 6

-- ВЫХОД --
{0: {1: 2}, 1: {0: 1}, 5: {6: 1}, 7: {6: 1}}
  1. Найти количество разных путей от вершины \(A\) до вершины \(B\). Эти вершины подаются в строчке после графа. Отсутствие ориентированных циклов гарантируется. Также разрешается применять рекурсию.

Пример:

-- ВХОД --
5
0 1
0 1
0 1
1 2
1 2
0 2

-- ВЫХОД --
6
  1. Найти какой-нибудь путь от вершины \(A\) до вершины \(B\) методом поиска в глубину. В графе могут присутствовать ориентированные циклы. Рекурсию использовать запрещено. Если пути нет, нужно напечатать НЕТ ПУТИ.

Пример:

-- ВХОД --
3
1 2
0 1
2 3
1 3

-- ВЫХОД --
1 2 3
  1. Найти нетривиальные (с более чем одной вершиной) связные компоненты графа. Каждую напечатать в виде возрастающей последовательности номеров её вершин.

Пример:

-- ВХОД --
5
3 2
2 1
1 0
5 6
7 6

-- ВЫХОД --
0 1 2 3
5 6 7

Решения

Задача 1

Определим сначала функцию для считывания графа в том формате, о котором мы договорились выше.

def read_graph_from_stdin():
    g = {}
    N = int(input())
    
    for i in range(N):
        a,b = map(int, input().split()) 
        if a not in g: g[a] = {}
        
        if b in g[a]: g[a][b] += 1
        else:         g[a][b]  = 1
    
    return g

В терминах этой функции решение первой задачи выглядит так:

def problem1():
    g = read_graph_from_stdin()
    print(g)

Задача 2

Решение второй задачи основывается на следующем: любой путь ненулевой длины от произвольной вершины v до пункта назначения представляет собой первый шаг (в соседнюю вершину u), за которым следует путь от u до пункта назначения. Поэтому количество путей от вершины v (не совпадающей с пунктом назначения) до пункта назначения представляет собой сумму количеств путей от соседей v до пункта назначения.

def problem2():
    g = read_graph_from_stdin()
    x,y = map(int, input().split())

    ## словарь, в который мы будем записывать количества путей
    path_count = {y: 1}  ## от вершины y до неё самой один путь
    
    ## функция, считающая количество путей от своего входа до y
    def traverse(v):
        if v in path_count: return path_count[v]
        if v not in g:      return 0

        s = sum(g[v][n] * traverse(n) for n in g[v])
        path_count[v] = s
        return s

    print(traverse(x))

Отметим, что мы могли обойтись более простой функцией traverse, не использующей словарь:

def traverse(v):
    if v == y:     return 1
    if v not in g: return 0
    
    return sum(g[v][n] * traverse(n) for n in g[v])

Основной недостаток такой версии: она каждую вершину посещает столько раз, сколько путей (не учитывающих кратность рёбер) есть до этой вершины. В то время как первая версия каждую вершину посещает столько раз, сколько в неё входит рёбер (без учёта кратностей), если эта вершина вообще достижима.

Задача 3

Для начала определим две вспомогательные функции. Первая функция печатает все элементы входной последовательности друг за другом:

def print_path(p): print(*p)

Напомним, что звёздочка перед формулой, поданной на вход функции, означает, что значение формулы следует воспринимать как последовательность, элементы которой нужно распределить по разным входам функции. Например, формула

foo(1, *[2,3,4])

означает то же самое, что и

foo(1,2,3,4)

Вторая функция выдаёт последовательность соседей указанной вершины графа:

def neighbors(g, v):
    if v not in g: return []
    else:          return g[v].keys()

Эта функция избавляет от необходимости делать лишние проверки вида

if v not in g: ...

которые легко забыть.

Решение третьей задачи представляет собой классический поиск в глубину.

def problem3():
    g = read_graph_from_stdin()
    x,y = map(int, input().split())

    path    = [x]
    visited = set()
    while path:
        current_v = path[-1]
        visited.add(current_v)
        if current_v == y: break

        to_visit = [n for n in neighbors(g,current_v)
                      if  n not in visited]

        if to_visit: path.append(to_visit[0])
        else:        path.pop()
        
    if path: print_path(path)
    else:    print("НЕТ ПУТИ")

Задача 4

Наконец, для решения четвёртой задачи нам пригодятся функции, получающие по графу список его рёбер и множество вершин его рёбер:

def edges(g):
    result = []
    for a in g:
        for b in g[a]:
            result.append((a,b))
            
    return result
    
def vertices(g):
    result = set()
    for a,b in edges(g):
        result.add(a)
        result.add(b)

    return result

Также определим функции, которая получает на вход отображение компонент, сопоставляющее каждой вершине её компоненту связности (т.е. множество вершин, достижимых из этой вершины), и печатает все различные компоненты связности.

def print_components(components):
    visited = set()
    for v in components:
        if v not in visited:
            print(*sorted(components[v]))
            visited |= components[v]

Осталось построить такое отображение компонент:

def problem4():
    g = read_graph_from_stdin()
    
    ## изначально "забываем" про все рёбра; 
    ## в таком случае компонента каждой вершины -- она сама
    components = dict((v,{v}) for v in vertices(g))

    ## теперь по очереди "вспоминаем" рёбра
    for a,b in edges(g):
        if b not in components[a]:
            ## объединяем компоненты обоих концов ...
            joint_component = (components[a] | components[b])
        
        ## ... и обновляем отображение компонент
        for x in joint_component:
            components[x] = joint_component

    print_components(components)