Блог пользователя aa0809

Ice Skating 217 A
Автор aa0809, история, 5 лет назад, По-английски

Hi,

I couldn't understand this problem from the editorial

https://codeforces.net/contest/217/problem/A

Can someone please explain how it's a bipartite graph

Thx

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The editorial says that you should divide points into groups such that in each group any pair of points are reachable from each other (maybe indirectly). If two points are on the same X- or Y- line, they should be in the same group. The answer is the number of groups minus one.

Example: 5 3 3 4 1 6 2 1 1 1 4

There are 3 groups: 1st: 4 1 1 1 1 4

2nd: 3 3

3rd: 6 2

Points 1 4 and 4 1 are reachable from each other because you can from one point first get to 1 1 and then to the other.

→ Ответить