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

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

HotLog


 

Независимое множество

(Время: 1 сек. Память: 16 Мб Сложность: 65%)

Понятие последовательно-параллельного графа является очень важным в таких разделах, как электротехника, дизайн микросхем, и других. Такие графы используются для задания электрических сетей, сетей передачи данных, и т. п.

В этой задаче граф может содержать параллельные ребра.

Последовательно-параллельные графы определяются рекурсивно следующим образом.

  1. Граф из двух вершин s и t, соединенных ребром st, является последовательно-параллельным графом с истоком s и стоком t. Обозначим этот граф как g.
  2. Если G1 является последовательно-параллельным графом с истоком s1 и стоком t1, а G2 является последовательно-параллельным графом с истоком s2 и стоком t2, то граф, получаемый объединением вершин t1 и s2 в одну, является последовательно-параллельным графом с истоком s1 и стоком t2, он обозначается SG1G2.
  3. Если G1 является последовательно-параллельным графом с истоком s1 и стоком t1, а G2 является последовательно-параллельным графом с истоком s2 и стоком t2, то граф, получаемый объединением вершин s1 и s2 в одну (обозначим ее как s12), и объединением вершин t1 и t2 в одну (обозначим ее как t12) является последовательно-параллельным графом с истоком s12 и стоком t12, он обозначается PG1G2.

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

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

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

Входной файл INPUT.TXT содержит одну строку описание последовательно-параллельного графа. Описание представляет собой корректное выражение, содержащее только буквы S, P и g. Длина выражения не превышает 105.

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

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

Пример

INPUT.TXTOUTPUT.TXT
1SPSgggPgg2

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 Шестая личная олимпиада
 Седьмая личная олимпиада
 Восьмая личная олимпиада
 Девятая личная олимпиада
 Десятая личная олимпиада
 Одиннадцатая личная олимпиада
 A. Юниты и ресурсы
 B. Великая таблица умножения
 C. Скобки (3)
 D. Независимое множество

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