Некоторые задачи

Здесь будут публиковаться разборы некоторых из задач из списка.

Разборы, приведённые здесь, отличаются от тех, что рассматривались на уроках: вместо заполнения плотной матрицы смежности здесь мы будем заполнять разреженную.

Программный интерфейс разреженной матрицы смежности

Для того, чтобы общаться с графом, мы будем использовать следующий интерфейс:

def empty_graph(n):
  return { (x+1): {} for x in range(n) }

def graph_size(g):
  return len(g)

def add_edge(g, v1, v2):
  if v2 in g[v1]: g[v1][v2] += 1
  else: g[v1][v2] = 1

def set_edge(g, v1, v2, e):
  g[v1][v2] = e

def get_edge(g, v1, v2):
  if v2 in g[v1]: return g[v1][v2]
  return 0

def neighbors(g, v):
  return [(n, g[v][n]) for n in g[v]]

Этот интерфейс отличается от edges_of_vertices/neighbors из предыдущего раздела. Основные отличия:

• вершинами являются не все целые числа, а только конечный их отрезок, начинающийся с единицы
• в матрице хранятся не сами рёбра, а только их кратности
• neighbors возвращает не только соседние вершины, но и кратности соответствующих рёбер

Ввод-вывод графов

Это по большей части задачи с E по H. Начнём с двух способов печати графа: как квадратной таблицы и как списка рёбер.

def print_graph_matrix(g):
  N = graph_size(g)

  for y in range(N):
    print(' '.join([
      str(get_edge(g, y+1,x+1)) for x in range(N)
    ]))

def print_graph_edges(g, directed=False):
  N = graph_size(g)
  
  for i in range(N):
    v = i+1

    for x,e in neighbors(g,v):
      if directed or v <= x:
        for _ in range(e): print(str(v), str(x))

Если не удалось понять, как работает вышеприведённая функция print_graph_matrix, предлагаем альтернативную реализацию:

def print_graph_matrix(g):
  N = graph_size(g)

  for y in range(N):
    for x in range(N):
      end = ' ' if x < N-1 else '\n'
      print(get_edge(g, y+1, x+1), end=end)

Теперь рассмотрим ввод графов в таком виде:

def read_graph_matrix_with_sizes():
  return read_graph_matrix(int(input()))

def read_graph_matrix(N):
  g = empty_graph(N)

  for i in range(N):
    numbers = [int(x) for x in input().split()]
    for j,e in enumerate(numbers):
      if e > 0: set_edge(g, i+1, j+1, e)

  return g

def read_graph_edges_with_sizes(directed=False):
  N, E = [int(x) for x in input().split()]
  return read_graph_edges(N,E,directed)

def read_graph_edges(N,E,directed=False):
  g = empty_graph(N)

  for i in range(E):
    v1, v2 = [int(x) for x in input().split()]
    add_edge(g, v1, v2)
    if not directed: add_edge(g, v2, v1)

  return g

В терминах этих функций задачи E, F, G, H решаются так:

def E():
  print_graph_edges(read_graph_matrix_with_sizes())

def F():
  print_graph_matrix(read_graph_edges_with_sizes())

def G():
  print_graph_edges(read_graph_matrix_with_sizes(), True)

def H():
  print_graph_matrix(read_graph_edges_with_sizes(True))

Ещё несколько задач

Задача B: есть ли в графе петли?

def B():
  if has_loops(read_graph_matrix_with_sizes()):
    print("YES")
  else:
    print("NO")

def has_loops(g):
  N = graph_size(g)

  for v in range(1,N+1):
    if get_edge(g, v, v) > 0: return True

  return False

Задача C: количество рёбер неориентированного графа.

def C():
  print(count_edges(read_graph_matrix_with_sizes()))

def count_edges(g):
  N = graph_size(g)

  total = 0
  for v in range(1,N+1):
    for x,count in neighbors(g,v):
      if x >= v: total += count

  return total

Задача I: разворот рёбер ориентированного графа, заданного списками смежности.

def read_inverted_graph_lists(N):
  g = empty_graph(N)

  for i in range(N):
    for x in input().split():
      v = int(x)
      add_edge(g, v, i+1) ## разворачиваем сразу при добавлении

  return g

def print_graph_lists(g):
  N = graph_size(g)

  for i in range(N):
    v = i+1
    
    for x,_ in sorted(neighbors(g,v)):
      print(x, end=' ')

    print()

def I():
  N = int(input())
  g = read_inverted_graph_lists(N)

  print(N)
  print_graph_lists(g)