有許多不同的描述和例子可以在線使用不相交集結構。 在某些情況下,對於每組,它存儲「等級」。當一個集合被合併到另一個集合中時,前者的等級增加1,如果他們是同一等級的話。 在其他情況下,對於每組,它存儲其大小。當一個集合被合併到另一個集合中時,它們的大小被添加。 Here它存儲排名。 在the wikipedia article中,它存儲等級。 In the Cornell University le
我沒有找到任何好的實現在C#中脫節集使用按級聯實現所以我實現了我自己的。它工作在O(log n)時間複雜度。 有沒有更快(或在C#中的內置實現)或我可以使用我自己的實現? class DisjointSetUBR
{
int[] parent;
int[] rank; // height of tree
public DisjointSetUBR(int[] ar