images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
05/12/2025 15:59:31

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1555. Конденсация графа

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вам задан связный ориентированный граф с `N` вершинами и `M` ребрами (`2\ ≤\ N\ ≤\ 20\ 000`, `N-1\ ≤\ M\ ≤\ 200\ 000`). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Граф задан во входном файле следующим образом: первая строка содержит числа `N` и `M`. Каждая из следующих `M` строк содержит описание ребра – два целых числа из диапазона от 1 до `N` – номера начала и конца ребра.
На первой строке выведите число `K` – количество компонент сильной связности в заданном графе. На следующей строке выведите `N` чисел – для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Пример ввода

6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4

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

2
1 1 1 2 2 2
loading