[データ構造とアルゴリズム解析(Mark Allen Weiss)]非交差@Python
1889 ワード
最も簡単な交差しない実現はMAWの「データ構造とアルゴリズム分析」から来ている.
コード:
コード:
class DisjSet:
def __init__(self, NumSets):
self.S = [0 for i in range(NumSets+1)]
def SetUnion(self, S, Root1, Root2):
S[Root2] = Root1
def Find(self, X, S):
if S[X] <= 0:
return X
else:
return self.Find(S[X], S)
DisjSet = DisjSet(8)
DisjSet.SetUnion(DisjSet.S, 5, 6)
DisjSet.SetUnion(DisjSet.S, 7, 8)
DisjSet.SetUnion(DisjSet.S, 5, 7)
print DisjSet.Find(8, DisjSet.S)
print DisjSet.Find(7, DisjSet.S)
print DisjSet.Find(4, DisjSet.S)
print DisjSet.S