در علم کامپیوتر یک داده ساختار از مجموعه‌های مجزا، اطلاعات تعدادی داده را که در تعدادی مجموعه مجزا تقسیم شده اند را نگه می‌دارد. سه عملیاتی که روی این داده ساختار تعریف می‌شود عبارتند از: پیدا کردن اینکه‌یک عنصر در کدام مجموعه قرار گرفته است ($ \text{Find} $)، ترکیب کردن دو تا از مجموعه‌های مجزا ($ \text{Union} $) و افزودن یک مجموعه جدید شامل تنها یک عضو ($ \text{MakeSet} $).

در این روش هر مجموعه را با یک لیست پیوندی نمایش می‌دهیم که عناصر موجود در آن مجموعه در آن لیست پیوندی قرار دارند. همچنین برای عناصر موجود در لیست ها یک آرایه تعریف می‌کنیم که خانه $i$ام آرایه اشاره‌گر به لیستی است که عنصر $i$ام قرار دارد. به این ترتیب برای عملیات $ \text{MakeSet} $ کافیست یک لیست جدید شامل یک عنصر بسازیم و همچنین یک خانه به آرایه اضافه کنیم که اشاره‌گر به لیست جدید باشد. برای عملیات $ \text{Find} $ هم کافیست مقدار خانه $i$ام آرایه که اشاره‌گر به لیستی است که عنصر $i$ام در آن قرار دارد را بر گردانیم. برای عملیات $ \text{Union} $ هم بدین ترتیب عمل می‌کنیم که آن مجموعه‌ای که اعضای کمتری دارد را درون مجموعه‌ای که اعضای بیشتری دارد قرار می‌دهیم. یعنی تک تک اعضای لیست پیوندی کوچک را به لیست پیوندی بزرگ اضافه کرده و اشاره‌گر آن‌ها را نیز به‌روزرسانی می‌کنیم. حال نکته‌ای که این کار دارد این است که به ازای یک عنصر، زمانی که از لیست کوچک به لیست بزرگتری فرستاده می‌شود، اندازه لیست جدیدش حداقل دو برابر لیست قدیمی‌اش است. بنابراین اگر تعداد کل عناصر $n$ باشد، هر عنصر در تمام عملیات‌ها حداکثر $\mathcal{O}(\log n)$ بار به یک لیست جدید اضافه می‌شود (چرا‌؟). بنابراین اگر $m$ تعداد کل عملیات‌ها از هر سه نوع باشد، این روش از مرتبه زمانی $\mathcal{O}(m + n \log n)$ می‌باشد.

در این روش هر مجموعه را بصورت یک درخت از اعضایش در نظر گرفته که یکی از اعضا ریشه می‌باشد. بنابراین همه‌ی مجموعه‌ها در کنار هم تشکیل یک جنگل را می‌دهند. برای هر عنصر $ \text{par}[x] $ را تعریف می‌کنیم که یکی از پدران عنصر $ x $ در درخت است (در واقع ما برای یک راس به دنبال ریشه درختی که آن راس در آن قرار گرفته هستیم و با استفاده از آرایه $ \text{par} $ این کار را انجام می‌دهیم). همچنین برای هر مجموعه یک $ \text{rank} $ تعریف کرده که توضیح آن در ادامه آمده است. به این ترتیب برای عملیات $ \text{MakeSet} $ یک خانه به آرایه $ \text{par} $ اضافه کرده و مقدار آن خانه را برابر شماره آن خانه قرار می‌دهیم زیرا یک درخت تک راسی به جنگل خود اضافه کرده‌ایم. همچنین یک خانه با مقدار صفر به آرایه $ \text{rank} $ اضافه می‌کنیم.

 function MakeSet(x)
     x.parent := x
     x.rank   := 0

برای ترکیب دو مجموعه که با دو عضوشان به ما داده شده‌اند، ابتدا ریشه درختی که آن دو عضو در آن هستند را با کمک $\text{Find}$ پیدا می‌کنیم. اگر دو مقدار برابر بدست آوردیم یعنی آن دو عضو از ابتدا در یک مجموعه بوده و نیاز نیست کاری بکنیم. اگر اینگونه نبود، آن مجموعه که $\text{rank}$ کمتری دارد را به مجموعه دیگر اضافه می‌کنیم.

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

برای عملیات $\text{Find}$ هم که قرار است ریشه درختی که عنصر مورد نظر در آن قرار دارد را پیدا کند، مطابق این تابع عمل می‌کنیم و همانطور که مشاهده می‌شود به ازای عناصری که در تابع بازگشتی زیر به آن‌ها برخورد می‌کنیم، مقدار $\text{par}$ همگی آن‌ها را به‌روزرسانی میکنیم.

 function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent

اثبات می‌شود در این الگوریتم، زمان انجام هر عملیات به طور میانگین از $\mathcal{O}(\alpha^{-1}(n))$ می‌باشد که در اینجا $\alpha$ تابع آکرمن و $\alpha ^ {-1}$ معکوس آن می‌باشد که می‌توان گفت برای تمام $n$ هایی که در مسائل با آن‌ها سر و کار داریم کمتر از $5$ می‌باشد.

از این مساله در مساله همبندی گراف و همچنین الگوریتم کروسکال برای محاسبه MST در یک گراف استفاده می‌شود.

• https://en.wikipedia.org/wiki/Disjoint-set_data_structure