\(X,Y\) 座標が一致する組を辺でつないだグラフを考えます。今は連結性のみが重要なので、同じ \(X,Y\) 座標の組に張る辺をまとめることが出来ます。

この時点で全ての地雷が連結になれば答えは \(N+1\) です。そうでないとき、新たに地雷を置くことで、連結成分のサイズのうち上位 \(2\) つをつなぐことが出来ます。また、\(3\) つ以上の連結成分をつなぐことは出来ない（もし出来るなら、別の連結成分で同じ \(X,Y\) 座標を共有する組が存在し矛盾）ので、これが上界をとります。

連結性をUnionFindなどで管理することで、この問題を \(O(N)\) で解くことが出来ます。