公式解説では、２つ隣までのみを考慮することでグラフの辺の本数を \(O(N)\) におさえていますが、別のやり方もあります。

\(x\) 座標全体と \(y\) 座標全体の合併集合を頂点とし、入力の点全体を辺とするグラフを \(\tilde G = ( \tilde V, \tilde E)\) を考えましょう。すなわち、

\[ \tilde { V } = \lbrace \xi _ 1, \dots, \xi _ {2 N + 1} \rbrace \sqcup \lbrace \eta _ 1, \dots, \eta _ {2 N + 1} \rbrace, \quad \tilde { E } = \lbrace ( \xi { X _ i }, \eta { Y _ i } ) \mid 1 \le i \le 2 N + 1 \rbrace \]

と定めると良いです。

すると関節点の代わりに橋を列挙する必要がありますが、これももちろん low-link で計算できますし、頂点数の代わりに辺の本数を数える必要がありますが、こちらも動的計画法で計算することができます。