在DAG中合併不可達頂點可能會創建循環？

Question

我有一個DAG（有向無環圖），其中我需要合併一些彼此不可達的頂點。我的最終圖應該是DAG。我的問題是通過做這個操作，做最後的圖可以有循環嗎？

Answer 1

如果你一次合併一對，在每一個之後重新檢查可達性，那麼不可能引入一個循環，因爲它必然涉及合併的頂點，這意味着它的弧會引起一個路徑在原始圖。

否則，轉換後的圖形可能會有一個循環。

A B 
| | 
| | 
v v 
B A 

合併A s。合併B s。