Дистанционный практикум по программированию

В некотором городе W узкие улицы, поэтому в городе организовано одностороннее движение. Но в связи с ремонтными работами по расширению дорог некоторые улицы перекрыты для проезда. На рисунке изображён пример расположения площадей и оставшихся улиц с указанным направлением движения.

 

 

Требуется найти количество областей, на которые стал разбит город - таких, что в каждой области с любой площади можно доехать до любой другой. В данном примере такими областями являются множества  {1,2,3}, {4} и {5,7,6}, при этом ответ будет 3.

 

Входные данные:  в первой строке количество площадей N (от 1 до 15) и количество дорог M. В каждой из следующих M строк записаны два числа u_i и v_i – начало и конец i-й дороги.

 

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

 

Пример входных данных:

7 10

1 2

2 3

2 5

2 4

3 1

3 4

4 5

5 7

6 5

7 6

 

Пример входных данных:

3

 

Автор: Опутина Т.Л.