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

# | User | Rating |
---|---|---|

1 | tourist | 3979 |

2 | Benq | 3623 |

3 | MiracleFaFa | 3604 |

4 | Radewoosh | 3545 |

5 | maroonrk | 3534 |

6 | slime | 3511 |

7 | greenheadstrange | 3430 |

8 | ecnerwala | 3342 |

9 | sunset | 3338 |

10 | xtqqwq | 3331 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 210 |

2 | Monogon | 200 |

3 | Um_nik | 193 |

4 | awoo | 191 |

5 | -is-this-fft- | 184 |

6 | sus | 177 |

7 | Errichto | 175 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 168 |

10 | SecondThread | 167 |

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

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/23/2022 22:25:21 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.