Вам задан ориентированный граф с \(N\) вершинами и \(M\) ребрами (\(1\le N\le 20 000\), \(1\le M\le 200 000\)). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Граф задан во входном файле следующим образом: первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк содержит описание ребра — два целых числа из диапазона от \(1\) до \(N\) — номера начала и конца ребра.
На первой строке выведите число \(K\) — количество компонент сильной связности в заданном графе. На следующей строке выведите \(N\) чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.
10 19 1 4 7 8 5 10 8 9 9 6 2 6 6 2 3 8 9 2 7 2 9 7 4 5 3 6 7 3 6 7 10 8 10 1 2 9 2 7
2 1 2 2 1 1 2 2 2 2 1
Изначально имеется дерево состоящее только из корня (вершина с номером \(1\)). Требуется научиться отвечать на следующие запросы:
Все номера вершин от \(1\) до \(N\).
В каждый момент времени у нас есть одно дерево.
В первой строке входного файла содержится число \(k\) — количество запросов. Следующие \(k\) строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит \(500\,000\).
Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.
9 ADD 1 2 ADD 1 3 ADD 2 4 GET 1 3 GET 2 3 GET 3 4 ADD 2 5 GET 4 5 GET 5 5
1 1 1 2 5
Э
то
интерактивная задача.
Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту.
Лабиринт состоит из N на M (1 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместится на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетке сработает сенсор и робот останется в той же клетке.
Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.
Протокол интерактивного взаимодействия
Программа должна выводить на стандартный вывод одну строку с действием робота и ждать строки в стандартном вводе с ответом, затем выводить очередную строку с действием и считывать ответ и так далее до тех пор, пока все проходимые клетки лабиринта не будут посещены. Программа должна завершать работу только когда все проходимые клетки будут посещены. Проходимые клетки могут быть посещены несколько раз. Допустимо передвигаться даже если все проходимые клетки уже посещены.
Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: SOUTH, WEST, NORTH, EAST, или DONE. Строка DONE должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу. Необходимо очищать выходной буфер после вывода каждой команды (flush).
Каждая строка входных данных представляет собой ответ на действие робота. Это может быть строка EMPTY если робот успешно переместился в заданном направлении или строка BLOCKED если робот не смог переместиться из-за того, что клетка, в которую он хотел попасть, непроходима.
Примеры
|
Входные данные |
Выходные данные |
|
NORTH |
BLOCKED |
Имеется неориентированный граф, состоящий из N вершин и M ребер. Необходимо проверить, является ли граф деревом. Напомним, что дерево — это связный граф, в котором нет циклов (следовательно, между любой парой вершин существует ровно один простой путь). Граф называется связным, если от одной вершины существует путь до любой другой.
Во входном файле в первой строке содержатся два целых числа N и M (1 ≤ N ≤ 100, 0 ≤ M ≤ 1000), записанные через пробел. Далее следуют M различных строк с описаниями ребер, каждая из которых содержит два натуральных числа Ai и Bi (1 ≤ Ai <Bi ≤ N), где Ai и Bi — номера вершин, соединенных i-м ребром.
В выходной файл выведите слово YES, если граф является деревом или NO в противном случае.
3 2 1 2 1 3
YES
Это интерактивная задача.
Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту. Лабиринт состоит из N на M (1 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместится на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетке сработает сенсор и робот останется в той же клетке. Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.
Протокол интерактивного взаимодействия
Программа должна выводить на стандартный вывод одну строку с действием робота и ждать строки в стандартном вводе с ответом, затем выводить очередную строку с действием и считывать ответ и так далее до тех пор, пока все проходимые клетки лабиринта не будут посещены. Программа должна завершать работу только когда все проходимые клетки будут посещены. Проходимые клетки могут быть посещены несколько раз. Допустимо передвигаться даже если все проходимые клетки уже посещены.
Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: SOUTH, WEST, NORTH, EAST, или DONE. Строка DONE должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу. Необходимо очищать выходной буфер после вывода каждой команды (flush).
Каждая строка входных данных представляет собой ответ на действие робота. Это может быть строка EMPTY если робот успешно переместился в заданном направлении или строка BLOCKED если робот не смог переместиться из-за того, что клетка, в которую он хотел попасть, непроходима.
Пример
| Выходные данные | Входные данные |
| NORTH | BLOCKED |