以下に示すソリューション（Pythonプログラムとして）は時間内に実行されますO(n lg*(n))。ここで、lg*(n)は、互いに素な集合のフォレストでのユニオン操作に関連付けられることが多い、ほぼ一定の反復対数関数です。
すべてのセルの最初のパスで、プログラムは、 Cormen / Leiserson / Riverstのエディション1のセクション22.3（Disjoint-set forests）で説明されているように、makeset(), findset(), link(),andと呼ばれるルーチンを使用して、disjoint-setフォレストを作成します。union()セルを通過する後のパスでは、各ばらばらのフォレストのメンバーの数をカウントし、深さなどをチェックします。最初のパスは時間内O(n lg*(n))に実行され、後のパスは時間内に実行されますO(n)が、単純なプログラム変更によって、一部のパスが実行される可能性がありますO(c)。O(b)合計b個のセルを持つc個の洞窟。
以下に示すコードは、前の回答に含まれるエラーの影響を受けないことに注意してください。前の回答の擬似コードには、次の行が含まれています。この行
if (size==0 and depth!=0) IsolatedCaveCount++
のエラーは、表面に接続された洞窟に地下の隆起した枝がある可能性があることです。もう1つの答えは、孤立した洞窟の総数に誤って追加されます。
以下に示すコードは、次の出力を生成し
Deepest: 5 Largest: 22 Isolated: 3
ます（図に示されている24のカウントは、4 + 9 + 9から22になるはずです）。
v=[0b0000010000000000100111000, # Cave map
0b0000000100000110001100000,
0b0000000000000001100111000,
0b0000000000111001110111100,
0b0000100000111001110111101]
nx, ny, nz = 5, 5, 5
inlay, ncells = (nx+1) * ny, (nx+1) * ny * nz
masks = []
for r in range(ny):
masks += [2**j for j in range(nx*ny)][nx*r:nx*r+nx] + [0]
p = [-1 for i in range(ncells)] # parent links
r = [ 0 for i in range(ncells)] # rank
c = [ 0 for i in range(ncells)] # forest-size counts
d = [-1 for i in range(ncells)] # depths
def makeset(x): # Ref: CLR 22.3, Disjoint-set forests
p[x] = x
r[x] = 0
def findset(x):
if x != p[x]:
p[x] = findset(p[x])
return p[x]
def link(x,y):
if r[x] > r[y]:
p[y] = x
else:
p[x] = y
if r[x] == r[y]:
r[y] += 1
def union(x,y):
link(findset(x), findset(y))
fa = 0 # fa = floor above
bc = 0 # bc = floor's base cell #
for f in v: # f = current-floor map
cn = bc-1 # cn = cell#
ml = 0
for m in masks:
cn += 1
if m & f:
makeset(cn)
if ml & f:
union(cn, cn-1)
mr = m>>nx
if mr and mr & f:
union(cn, cn-nx-1)
if m & fa:
union(cn, cn-inlay)
ml = m
bc += inlay
fa = f
for i in range(inlay):
findset(i)
if p[i] > -1:
d[p[i]] = 0
for i in range(ncells):
if p[i] > -1:
c[findset(i)] += 1
if d[p[i]] > -1:
d[p[i]] = max(d[p[i]], i//inlay)
isola = len([i for i in range(ncells) if c[i] > 0 and d[p[i]] < 0])
print "Deepest:", 1+max(d), " Largest:", max(c), " Isolated:", isola
