<ПРЕД Задача:
СЛЕД>
Задачу решили 15 пользователей: Mirzakhmet, fboy123, Zhukov_Dmitry, wInuX, WsemirZ, zloy_mipt, mazahaka, defrager, yiuyuho, murphy, Dest, LiuChenheng, dragonic, avi2011class, rayaryabinina.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Планарность графа

Time limit = 30 секунд(ы)

Проверить планарен ли граф.

Вход. Описание графа в следующем формате:

V E
s1 e1
s2 e2
...
sE eE
где V — число вершин (V < 3000), E — число рёбер (E < 10000), (si, ei) — описание i-го ребра. Вершины обозначаются числами 0, 1, ..., (V-1).

Выход. Одна строчка со словом "YES", если граф планарен, и "NO" — иначе.

Вход#1
2 1
0 1

Выход#1
YES


Вход#2
6 9
0 3
0 4
0 5
1 3
1 4
1 5
2 3
2 4
2 5
Выход#2
NO

Автор:
Классическая задача, тесты и описание -- Егор Цветков.
19 апреля 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 220ms

SW soft NIX
ID = 52.3.228.47