Примеры входа и выхода

Упражнение «Поиск в ширину»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

Дан неориентированный граф.

- Поиском в ширину найти кратчайшие пути из заданной вершины до всех остальных вершин.

- Поиском в ширину найти компоненты связности графа.

Вход

В первой строке текстового файла записано количество вершин графа N(1 ≤ N ≤ 1000). В следующих N строках записаны списки смежных вершин в формате: K v₁ v₂ ... v_Kгде K - длина списка, v_i - номер вершины, смежной с данной.

Выход

Запишите в выходной файл:

- Кратчайшие пути из вершины N во все остальные вершины, путь вывести в формате: K v₁ v₂ … v_K , где K– длина пути (количество рёбер), v_i – вершины, составляющие путь (вершину N выводить не нужно). Если некоторая вершина не достижима из вершины N, вывести число 0;

- Количество связных компонент графа.

Примеры входа и выхода

Упражнение «0,1-BFS»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

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

Вход

В первой строке входного файла записано целые числа N – количество вершин графа и M – количество рёбер графа (2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁶). Остаток файла содержит описание M рёбер. Каждое ребро задано тройкой целых чисел u, v, d, где u, v – номера вершин (1 ≤ u, v≤ N, u ≠ v), d – длина ребра (d = 0 | 1).

Выход

Запишите в выходной файл минимальное расстояние между вершинами 1 и N графа. Если не существует пути в графе от вершины 1 до вершины N, запишите в выходной файл число -1 (минус единица).

Примеры входа и выхода

Упражнение «Поиск в глубину»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

Дан неориентированный граф. Поиском в глубину найти компоненты связности графа.

Вход

В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 1000). В остальных строках записаны рёбра графа. Каждое ребро задано парой натуральных чисел u, v (1 ≤ u, v ≤ N, u ≠ v).

Выход

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

Примеры входа и выхода

Упражнение «Сильно связные компоненты»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 3 секунды на тест

Дан орграф. Найти сильно связные компоненты орграфа.

Вход

В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 10⁵). В следующих N строках записаны списки смежных вершин в формате: K v₁ v₂ ... v_K, где K - длина списка, v_i - номер вершины, смежной с данной вершиной. Суммарное количество дуг не превосходит 5·10⁶.

Выход

В выходной файл запишите количество сильно связных компонент орграфа.

Примеры входа и выхода

Упражнение «Точки сочленения и мосты»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

Дан неориентированный граф.

- Найти все его точки сочленения.

- Найти все его мосты.

- Найти двусвязную компоненту, в которую входит первая вершина.

Вход

Во входном файле записано количество вершин графа N (1 ≤ N ≤ 1000) и список ребер графа. Каждое ребро задано парой натуральных чисел u, v (1 ≤ u, v ≤ N).

Выход

В выходной файл запишите:

- номера вершин графа, являющихся точками сочленения (в порядке возрастания);

- ребра графа, являющиеся мостами (в порядке не убывания меньшего номера вершины, для одинаковых меньших номеров в порядке возрастания большего номера вершины);

- номера вершин, входящих в двусвязную компоненту, порожденную вершиной 1 (в порядке возрастания).

Примеры входа и выхода

Лабораторная работа «Топологическая сортировка»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

Выполнить топологическую сортировку заданного орграфа.

Вход

В первой строке входного файла записано количество вершин графа n и количество дуг m (1 ≤ n ≤ 10⁵, 0 ≤ m≤ 10⁶). В остальных строках файла записано mпар целых чисел u, v (1 ≤ u, v ≤ n, u ≠ v). Пара чисел u, vзадаёт дугу (u, v).

Выход

В выходной файл запишите результаты номера вершин графа в порядке топологической сортировки. Если задача имеет несколько решений, выведите любое из них. Если задача не имеет решения, запишите в файл одно число -1 (минус единица).

Примеры входа и выхода

Поиск по сайту: