2231. 试炼之地

题目背景

在试炼之地中,试炼刷怪笼可能会刷出大量旋风人(Breeze);要解决这些生物相当困难,但我可以偷偷告诉你一个诀窍......

题目描述

在一片开阔的试炼场中,固定了 n 个旋风人;当旋风人被激怒之后,会向东西南北四个正方向发射四枚风弹。风弹可以激怒更多旋风人,也可以打破你部署的麦旋风。当你的麦旋风被打破时,同样会分裂成四枚风弹飞向四个方向。

如果单个被激怒的旋风人会波及场上所有旋风人,场上的风元素便会失去控制,导致所有旋风人爆体而亡,你的任务是部署尽可能少的风弹,使得任意一个旋风人被激怒后能连锁到所有敌人。

形式上,在一个二维平面上分布有 n 个目标,x 坐标或 y 坐标相同的目标两两相连,问最少添加多少个目标,使得所有目标连锁。

输入

麦旋风并不想为难大家,所以本题单测,输入共 n + 1 行。

第一行包含一个整数 n (1 \leq n \leq 100) - 旋风人的数量。

接下来的 n 行,每行两个整数 x, y (1 \leq x, y \leq 1000) - 旋风人所在的位置。

输出

输出一行一个非负整数,表示激怒所有旋风人需要添加的最少的麦旋风数量。

样例

标准输入 复制文本
4
2 1
1 2
2 3
3 4
标准输出 复制文本
2
标准输入 复制文本
1
1000 1000
标准输出 复制文本
0

提示

  • 在第一组数据中:在 (2, 2) 部署麦旋风连锁 (2, 1),(1, 2),(2, 3);在 (2, 4) 部署麦旋风连锁 (2, 1),(2, 3),(3, 4);此时任意一个旋风人被激怒,即可连锁到所有旋风人。可以证明不可能消耗更少的麦旋风来完成任务。

  • 在第二组数据中:场上只有一名旋风人,它被激怒时自己就爆体而亡了,不需要浪费麦旋风。

为什么用麦旋风能解决旋风人?我不知道。

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 202
通过 58