Question

Формула N Оценка за задачу: 30 баллов В гонках "Формулы N" участвует N машин. В результате квалификационного заезда машины получили порядковые номера и стартовали в порядке от 1 до N. Вася - страстный поклонник гонок, но у него в общежитии плохой интернет и он не может смотреть видео-трансляцию. Поэтому он вынужден читать текстовую трансляцию, в которой все сообщения имеют вид "Машина номер X обогнала машину номер Y". Вася ненадолго отвлекся и перестал понимать текущий порядок машин на трассе. Помогите ему понять, в каком порядке расположены машины по известным сообщениям с начала текстовой трансляции. Формат входных данных В первой строке заданы два натуральных числа N и M (1 ≤ N, M ≤ 100000) - количество машин и сообщений об обгоне соответственно. В следующих M строках содержатся описание сообщений об обгоне: пары чисел X и Y (1 ≤ X, Y ≤ N) - машина X обогнала машину Y. Гарантируется, что машина Y ехала непосредственно перед машиной X на момент сообщения. Формат результата Выведите N чисел - порядок, в котором находятся машины после обработки всех сообщений. Примеры Входные данные 3 4 2 1 3 1 3 2 1 2 Результат работы 3 1 2

Answer 1

Var
  n, m, x, y, i: int64;
   ar: array[1..100000]of int64;
  ms: array[1..100000]of int64;
 begin
  read(n, m);
  for i := 1 to n do
   begin
    ar[i] := i;
    ms[i] := i;
   end;
  for i := 1 to m do
   begin
    read(x, y);
    swap(ms[x], ms[y]);
     swap(ar[ms[x]], ar[ms[y]]);
   end;
  for i := 1 to n do write(ar[i], ' ');
 end. 

Answer 2

Для решения этой задачи можно использовать алгоритм топологической сортировки. Начнем с создания графа, в котором вершины будут представлять машины, а ребра - сообщения об обгонах. Затем применим топологическую сортировку для этого графа, чтобы определить порядок машин на трассе.

Пример кода на Python:

from collections import defaultdict

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

queue = [node for node in graph if in_degree[node] == 0]
    result = []

while queue:
        node = queue.pop(0)
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

if len(result) != len(graph):
        return "Граф содержит цикл, невозможно упорядочить"

return result

def main():
    N, M = map(int, input().split())
    graph = defaultdict(list)

for _ in range(M):
        X, Y = map(int, input().split())
        graph[Y].append(X)

result = topological_sort(graph)
    print(*result)

if __name__ == "__main__":
    main()

Пример входных данных: 3 4 2 1 3 1 3 2 1 2

Результат работы: 3 1 2

Этот код считывает количество машин и количество сообщений об обгонах, затем считывает сами сообщения и выводит порядок машин после обработки всех сообщений.