0
給定連通圖G =（V，E），我想要找到所有的1-切割。 1切僅僅是一個單獨的邊緣，其去除將G分成2個連接的組件。檢測無向圖中所有1-切割的高效算法
我現在使用的算法是依次刪除每條邊，然後使用DFS檢查它的兩個端點是否位於相同的連接組件中。運行在O（E（V + E））時間。這個速度已經快於我在Nagamochi，Nishimura和Ibaraki（1998）的min-cut文獻中找到的最佳算法，它需要O（VE（V + E））時間。他們的算法適用於任何尺寸的所有最小切割。我只需要我的1張剪貼畫就有效。
有沒有人知道哪裏有更好的算法？我的使用案例的另一個特點可能是有用的，那就是我使用的圖表往往具有非常小的反饋弧集。如果我有算法的運行時間取決於反饋弧集的大小，那也是有用的。