Кратчайший путь в невзвешенном графе

[йцукенг87]

Кратчайший путь в невзвешенном графе
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Дан ориентированный невзвешенный граф. Также даны стартовая и конечная вершина. Найдите и выведите кратчайший путь между этими двум вершинами.

Входные данные
В первой строке даны n и m — число вершин и ребер в графе (1≤n≤105,0≤m≤2⋅105). В следующих m строках идут пары чисел, задающие ребра.

В последней строке даны s и t — номера стартовой и конечной вершины (1≤s,t≤n,s≠t).

Выходные данные
Если пути не существует, выведите «-1» без кавычек. Иначе в первой строке выведите длину кратчайшего пути, а в следующей — вершины пути, включая стартовую и конечную.

Пример
входные данныеСкопировать
5 5
1 2
2 3
3 4
1 5
5 4
1 4
выходные данныеСкопировать
2
1 5 4

[Пётр Седов]

Так это получается просто поиск в ширину. На C++ можно так:

#include <vector>
#include <queue>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

struct edge_t;

struct vert_t {
  edge_t* edges_first; // список исходящих рёбер
  vert_t* prev_in_path;
};

struct edge_t {
  edge_t* next;
  vert_t* vert_2;
};

vector<vert_t> _verts;
vector<edge_t> _edges;
int _cur_edge_index;

void init_graph(int verts_count, int edges_count) {
  _verts.resize(verts_count);
  for (int i = 0; i < verts_count; i++) {
    vert_t* v = &_verts[i];
    // в новых компиляторах можно использовать nullptr
    v->edges_first = NULL; // изначально список пустой
    v->prev_in_path = NULL;
  }
  _edges.resize(edges_count);
  _cur_edge_index = 0;
}

vert_t* get_vert(int vert_id) {
  bool valid = (1 <= vert_id) && (vert_id <= _verts.size());
  if (!valid) {
    // упрощённая обработка ошибки; во «взрослых» программах в таких случаях могут кинуть исключение (exception)
    printf("Invalid vertex id %i.\n", vert_id);
    exit(1);
  }
  return &_verts[vert_id - 1];
}

void add_edge(int vert_1_id, int vert_2_id) {
  vert_t* v1 = get_vert(vert_1_id);
  vert_t* v2 = get_vert(vert_2_id);
  edge_t* e = &_edges[_cur_edge_index++];
  // добавляем ребро в список
  e->next = v1->edges_first;
  v1->edges_first = e;

  e->vert_2 = v2;
}

// аналог NULL
vert_t* const _stop_marker = reinterpret_cast<vert_t*>(1);

// количество рёбер в пути
int path_len(const vert_t* vert) {
  int verts_count = 0;
  for (const vert_t* v = vert; v != _stop_marker; v = v->prev_in_path) {
    verts_count++;
  }
  return verts_count - 1;
}

void print_path(const vert_t* vert) {
  const vert_t* prev = vert->prev_in_path;
  if (prev != _stop_marker) {
    print_path(prev);
    printf(" ");
  }
  int vert_id = 1 + (vert - &_verts.front()); // в новых компиляторах можно использовать метод std::vector::data
  printf("%i", vert_id);
}

int main() {
  int start_vert_id, target_vert_id;
  if (true) {
    int verts_count, edges_count;
    scanf("%i %i", &verts_count, &edges_count);
    init_graph(verts_count, edges_count);
    for (int i = 0; i < edges_count; i++) {
      int vert_1_id, vert_2_id;
      scanf("%i %i", &vert_1_id, &vert_2_id);
      add_edge(vert_1_id, vert_2_id);
    }
    scanf("%i %i", &start_vert_id, &target_vert_id);
  } else {
    // тестовый пример
    init_graph(5, 5);
    add_edge(1, 2);
    add_edge(2, 3);
    add_edge(3, 4);
    add_edge(1, 5);
    add_edge(5, 4);
    start_vert_id = 1;
    target_vert_id = 4;
  }

  vert_t* start_vert = get_vert(start_vert_id);
  vert_t* target_vert = get_vert(target_vert_id);
  if (start_vert == target_vert) {
    printf("0\n%i\n", start_vert_id);
    return 0;
  }

  queue<vert_t*> boundary_verts;
  start_vert->prev_in_path = _stop_marker;
  boundary_verts.push(start_vert);
  do {
    vert_t* v = boundary_verts.front();
    boundary_verts.pop();
    for (edge_t* e = v->edges_first; e != NULL; e = e->next) {
      vert_t* v2 = e->vert_2;
      if (v2->prev_in_path == NULL) {
        v2->prev_in_path = v;
        if (v2 == target_vert) {
          printf("%i\n", path_len(v2));
          print_path(v2);
          printf("\n");
          return 0;
        }
        boundary_verts.push(v2);
      }
    }
  } while (!boundary_verts.empty());
  // путь не найден
  printf("-1\n");
  return 0;
}