標準のユニオン/検索またはディスジョイント セットのO(1)データ構造は、シングル スレッドの場合、(事実上) 実行時間が非常に長くなります。ただし、マルチスレッドの場合の有効性/パフォーマンスはどうですか? ロックやアトミック ポインター サイズの書き込み以外のアトミック操作がなくても、完全に有効だと思います。
次のロジックに問題がある人はいますか?
最初に、ポインター サイズの書き込みはアトミックであると仮定します。
findそのことから、発生する唯一の更新はすべて同じ値に設定されるため、関数を複数のスレッドで安全に実行できると主張するのは難しくありません。find関数が呼び出されたとき (返されたときではなく) に true だった答えを返すことを許可する場合、多くfindの s と 1 つの s をunion同時に実行できると主張するのは難しくありません。sの引数findは変更されず、unionのみがルートを更新し、finds はルートを更新しません。残りのケース（数
union秒）については、それもうまくいくと思いますが、よくわかりません。
ところで: ソリューションがシングル スレッド バージョンと同じくらい効率的である必要はありません。(ロック/アトミックを回避するために、グローバルにコヒーレントな状態も喜んで破棄します。)
編集：別の見方をすると、新しいルートではない側が（ルートとしてではなく）他の何かと結合されている場合、2番目の結合の反対側からそれを切り離すことができるため、多結合のケースは機能しません.
A = find(a) // union 1
B = find(b) // union 1
----
X = find(x) // union 2 (x == a) -> (X == A) -> (X.par aliases A.par)
Y = find(y) // union 2
X.par = Y // union 2
----
A.par = B // union 1
これはCASで回避できます:
while(!CAS(A == A.par, B)) A = find(A);