連結グラフからノードをひとつずつ取り除くことを考える。このとき、連結性を保ったまま、ノード数が1になるまでグラフを小さくできる。
ノードを取り除く順番次第で、グラフが連結ではなくなってしまう。例えば上の図で最初にEを取り除くと、グラフが連結ではなくなる。では連結性を保ちたいとき、どのような順番でノードを取り除けばよいか？
グラフのあるノードからBFSもしくはDFSをすると木ができる。この木の葉をひとつずつ摘んでいくと、最終的に根が残る。木の葉を摘むときに、元のグラフの対応するノードを削除していくと、連結性を保ったままノード数を減らし続けることができる。以下は元のグラフをAからDFSしたときにできる木を示している。
D,F,B,E,Cの順に葉を摘むと、元のグラフが1枚目の画像のように遷移する。
(参考) LeetCode 947. Most Stones Removed with Same Row or Column