Hi,
I couldn't understand this problem from the editorial
https://mirror.codeforces.com/contest/217/problem/A
Can someone please explain how it's a bipartite graph
Thx
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
Hi,
I couldn't understand this problem from the editorial
https://mirror.codeforces.com/contest/217/problem/A
Can someone please explain how it's a bipartite graph
Thx
Название |
---|
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.