Union-Find (Disjoint Set Union) ਤੱਤਾਂ ਦੀ ਵੰਡ ਨੂੰ disjoint sets ਵਿੱਚ ਟਰੈਕ ਕਰਦਾ ਹੈ ਅਤੇ ਦੋ ਲਗਭਗ-O(1) operations ਨੂੰ ਸਪੋਰਟ ਕਰਦਾ ਹੈ: find (x ਕਿਸ set ਵਿੱਚ ਹੈ?) ਅਤੇ union (ਦੋ sets ਨੂੰ ਮਿਲਾਓ)। ਇਹ connectivity queries ਵਿੱਚ ਸ਼ਾਨਦਾਰ ਹੈ।
ਵਿਚਾਰ
ਹਰੇਕ set ਇੱਕ ਪ੍ਰਤੀਨਿਧੀ root ਵਾਲਾ ਰੁੱਖ ਹੈ। ਅਤੇ ਦੇ ਨਾਲ, operations ਲਗਭਗ ਸਥਿਰ ਸਮੇਂ ਚਲਦੇ ਹਨ (inverse Ackermann, α(n))।
