aa0809's blog

By aa0809, history, 4 years ago, In English

Hi,

I couldn't understand this problem from the editorial

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

Can someone please explain how it's a bipartite graph

Thx

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.