如何確定與傳遞關係的合併 - 查找

Question

我有以下數據集

6 - 7 -->means 6 and 7 are related 
5 - 4 -->means 5 and 4 are related 
4 - 6 -->means 4 and 6 are related 

現在我該怎樣確定5使用的合併 - 查找有關7？有人請指導我。

Answer 1

您不必在此處使用Union-Find。您可以使用基本的DFS標記一個連接組件中的每個訪問頂點，並使用此組件中從其開始的頂點索引DFS。這種方法在輸入大小方面是線性的，所以它總是比任何Union-Find的實現更快。

但是，如果您想通過Union-Find來完成，請在您輸入的每個邊沿x-y處撥打電話Union(x, y)。在處理完所有邊後，如果要查明頂點a是否與a頂點b有關，即是否存在以a開始並以b結尾的邊連接的頂點序列，請檢查是否Find(a) == Find(b)。這種方法的複雜性取決於你如何實現Union-Find數據結構。最好的實現幾乎可以達到線性時間，實際上它被認爲是線性算法。