SZ#G6DFS14. 【GESP强化 六级】连接所有滑行点

提交1 通过1
通过率100%
时间限制2000ms
内存限制256MiB

题目描述

小泽正在练习一种只能横向或纵向滑行的游戏。场地中已有 NN 个落脚点,第 ii 个点位于整数坐标 (xi,yi)(x_i,y_i),所有坐标互不相同。若两个落脚点横坐标相同或纵坐标相同,小泽就能从其中一个直接滑到另一个;也可以通过若干落脚点间接到达。

小泽可以在任意整数坐标增加新的落脚点。请计算最少增加多少个点,才能让任意一个已有落脚点都可以到达其他所有已有落脚点。

输入格式

第一行输入 NN

接下来 NN 行输入 xi,yix_i,y_i

输出格式

输出最少需要增加的落脚点数量。

6
1 0
11 10
2 1
11 11
2 2
11 12
2
9
1 0
11 10
22 21
1 1
12 12
21 22
1 3
11 13
22 24
4
12
1 0
11 10
22 21
31 31
2 2
11 12
21 23
31 33
2 4
11 14
22 25
31 35
5

数据范围与约定

  • 1N1001 \le N \le 100
  • 1xi,yi10001 \le x_i,y_i \le 1000
  • 坐标两两不同