Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Обход в глубину
    Компоненты сильной связности(3 задач)
    Мосты(2 задач)
    Применение обхода в глубину(3 задач)
    Топологическая сортировка(2 задач)
    Точки сочленения(1 задач)
---> 7 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада
    8 класс(18 задач)
    9-11 классы(228 задач)
Страница: 1 2 >> Отображать по:
#42
Красно-синий граф
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано N точек. Из каждой точки исходят красные или синие ребра во все точки с большим номером. Требуется определить, существует ли пара точек такая, что из первой можно добраться до второй как по красным ребрам так и по синим.

Даны N точек, занумерованных числами 1, 2, ..., N. От каждой точки с меньшим номером к каждой точке с большим номером ведет стрелка красного или синего цвета. Раскраска стрелок называется однотонной, если нет двух таких точек A и B, что от A до B можно добраться как только по красным стрелкам, так и только по синим.

Ваша задача — по заданной раскраске определить, является ли она однотонной.

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

В первой строке входных данных содержится единственное число N (3 ≤ N ≤ 5000).

В следующих N–1 строках идет описание раскраски. В (i+1)-й строке  записано (N–i) символов R (красный) или B (синий), соответствующих цвету стрелок, выходящих из точки i и входящих в точки (i+1), (i+2), ..., N соответственно.

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

Выведите YES, если приведенная раскраска является однотонной, и NO в противном случае.

Оценка задачи

1 балл будут набирать решения, верно работающие для N ≤ 50.

Примеры
Входные данные
3
RB
R
Выходные данные
NO
Входные данные
3
RR
R
Выходные данные
YES
#858
Свинки-копилки
  
Подсчет количества циклов в графе, где у каждой вершины ровно одно исходящее ребро.

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.

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

В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

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

Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Пример

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

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

Комментарий

4

2

1

2

4

2

Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.

Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
#859
Трехцветные таблицы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Прямоугольную таблицу, состоящую из N строк и M столбцов, раскрашивают следующим образом. Каждый столбец таблицы и каждую строку красят либо в синий, либо в желтый цвет. В итоге клетки, оказавшиеся на пересечении синего столбца и синей строки оказываются синими, желтого столбца и желтой строки — желтыми, а клетки на пересечении синего столбца и желтой строки, или, наоборот, желтого столбца и синей строки — зелеными.

Раскраска всех клеток таблицы (или просто сама таблица) называется правильной, если она может быть получена описанным выше способом.

Вам дана прямоугольная таблица, которую нужно раскрасить таким образом. Про некоторые клетки известно, какого цвета они должны быть, а остальные клетки могут в итоге быть любого цвета. Определите, сколько существует различных правильных таблиц, в которых нужные клетки покрашены в нужный цвет.

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

Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:

0 — клетка может в итоге быть любого цвета

1 — клетка должна быть синей

2 — клетка должна быть желтой

3 — клетка должна быть зеленой

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

Выведите одно число — количество различных правильных таблиц, в которых нужные клетки покрашены в нужный цвет. Обратите внимание, что если два или более способов раскраски столбцов и строк таблицы приводят к одинаковой раскраске самой таблицы, то это нужно считать как один вариант раскраски таблицы (см. пример 2).

Примеры

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

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

3 4

1 0 0 0

3 0 0 0

0 0 0 0

16

2 2

3 3

3 3

1

2 2

2 2

2 3

0
#865
Свинки-копилки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан ориентированный граф, в котором у каждой вершины существует ровно одно исходящее ребро. Требуется найти количество циклов в нем.

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.

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

В первой строке содержится число N — количество свинок-копилок (1≤N≤100). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

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

Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Пример

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

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

Комментарий

4

2

1

2

4

2

Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.

Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
#1190
Введите одностороннее движение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В Тридевятом Царстве было N городов, некоторые из которых были соединены дорогами. К сожалению, в последнее время добраться из одного города в другой стало очень сложно из-за возникших автомобильных пробок. В целях борьбы с пробками было решено все дороги сделать односторонними, т.е. разрешить проезд по каждой дороге только в одном направлении. При этом требуется, чтобы по-прежнему можно было из любого города попасть в любой другой.

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

Во входном файле записано сначала число N — количество городов (1≤N≤1000). Затем записано число M — количество дорог (1≤M≤100000). Далее идет M пар чисел, задающих дороги (каждая дорога описывается номерами городов, которые она соединяет). Не бывает дорог из некоторого города в тот же город. Между двумя городами может быть несколько дорог. Гарантируется, что до введения одностороннего движения можно было попасть из любого города в любой другой.

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

В выходной файл нужно выдать M пар чисел, соответствующих дорогам (дороги должны быть выданы в том же порядке, в котором они заданы во входном файле). Для каждой дороги сначала должен быть записан номер города, из которого по ней можно будет уехать после введения одностороннего движения, а затем — номер города, куда эта дорога ведет.

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

Примеры
Входные данные
4
6
1 2
1 2
2 3
2 4
4 3
1 4
Выходные данные
2 1
2 1
3 2
4 2
4 3
1 4
Входные данные
2
1
1 2
Выходные данные
0
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест