問題タブ [disjoint-union]

最近、ツリーで DSU とそのアプリケーションに出くわしました。関連する問題を解決していたときに、一部で Time Limit Exceeded エラーが発生したので、チュートリアルをもう一度読んだところ、通常の結合の即興バージョンが加重結合であることがわかりました。 . この加重結合操作では、小さいサイズのサブセットのルートを、(2 つのうちの) 大きいサイズのサブセットのルートの子として作成します。それはどのように私たちに利益をもたらしますか? チュートリアルへのリンク

n 個のノードとn個のエッジを持つ無向連結グラフが与えられます。2 つのノードaとbが与えられます。a から b へのパスにあるが、サイクルの一部ではないエッジの数を見つけます。（エッジの数がnであるため、確かにサイクルがあります）。これは dsu データ構造によって実行できますか? エッジを削除すると a と b が切断される場合、それを答えとして数えることができます。前もって感謝します。