Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

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

(Время: 3 сек. Память: 32 Мб Сложность: 70%)

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

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1 ≤ N ≤ 20 000, 1 ≤ M ≤ 200 000) – число вершин и ребер соответственно. Каждая из следующих M строк содержит описание ребра: два целых числа из диапазона от 1 до N – номера начала и конца ребра.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите число K – количество компонент сильной связности в заданном графе. На следующей строке выведите N чисел – для каждой вершины от 1 до N выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Пример

INPUT.TXTOUTPUT.TXT
110 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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Ковбои
 B. Маршрут для гонца
 C. Конденсация графа
 D. Манхэттенский полицейский

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru



Недорогих и хороших Платных VPN.