DSU

DSU یا Disjoint-set/Union-find که به آن مجموعه های مجزا هم می گویند یک الگوریتم کاربردی برای مسائل همبندی گراف و همچنین برای محاسبه MST است.

این الگوریتم دو دستور اصلی ادغام و جستجو دارد. در این الگوریتم هر مجموعه یک نماینده دارد.

روش های اجرای DSU

قبل از شروع باید این نکته را ذکر کنم که دو روش مشهور برای اجرای DSU مورد استفاده است که یکی لیست و دیگری جنگل است. در لیست هر عضو مجموعه در یک لیست قرار می گیرند و یک آرایه نیز وجود دارد که نشان می دهد نماینده عضو x چه عضوی است به طور مثال \(Rep[x] = X\) . و روش دیگر جنگل است که هر عضو را راس در نظر می گیریم و در هر مجموعه یک درخت داریم که تمامی راس های آن تمامی عضو های مجموعه آن است و این مجموعه از یک راس آویخته شده(نماینده مجموعه) و بقیه راس ها هر کدام یک پدر دارند و کافیست که یک آرایه نگه داریم که نشان می دهد که پدر هر کس چه راسی است(پدر راسی که در درخت پدر ندارد(نماینده مجموعه) را هم می توان خودش گذاشت تا بدانیم که نماینده درخت است). \(Par[x] = X\)

دستور ها

جستجو (Find)

دستور جستجو برای پیدا کردن نماینده یک عضو استفاده می شود. به این صورت که هنگامی که نیاز دارید تا بدانید نماینده مجموعه شامل عضو x کیست از آن استفاده می کنید.

  • روش اول که برای لیست به کار می رود به این نحو است که فقط کافیست مقدار آرایه \(Rep[x]\) را برگردانیم.
int Find(int x){
    return Rep[x];
}
  • روش دوم که برای جنگل مورد استفاده قرار می گیرید به این نحو است که باید در هر مرحله از طریق آرایه Par به پدران راس \(x\) برویم تا به ریشه(نماینده مجموعه) برسیم. حال اگر از تابع بازگشتی برای این کار استفاده کنیم می توان اردرمان را بهتر کنیم. به این روش که وقتی به دنبال ریشه \(x\) هستیم در انتها پدر x را برابر با ریشه کنیم. این روش که Path Compression نام دارد باعث می شود تمام راس هایی که در مسیر x تا ریشه هستند پدر خود را به ریشه تغییر دهند، در این صورت تعداد بچه های ریشه زیاد می شود. با این روش مسیر x به ریشه کوتاه تر می شود (برای درک بهتر این قسمت تابع Find را ببینید) و باعث می شود میانگین انجام هر عملیات در مسائلی که با آنها سر و کار داریم به کمتر از ۵ برسد.
int Find(int x){
    if(Par[x] != x)
        Par[x] = Find(Par[x]);
    return Par[x];
}

ادغام (Union)

دو مجموعه را با هم ادغام می کند و مجموعه جدید را تشکیل می دهد. فرض کنید که دو مجموعه که شامل دو عضو x و y است را با هم ادغام کنیم.

  • در ابتدا نماینده این دو عضو را پیدا می کنیم. فرض کنید به ترتیب X و Y باشند. اگر X و Y یکی باشند به این معناست که این دو عضو در یک مجموعه هستند و لازم نیست که ادغامی انجام دهیم. اگر برابر نبودند نماینده اعضای مجموعه ای را برابر با نماینده اعضای مجموعه دیگر میکنیم. نکته ای که وجود دارد این است که نماینده مجموعه ای را تغییر می دهیم که تعداد اعضای کمتری دارد، به این دلیل که اردر این عمل \(O(n lgn)\) است (نماینده هر عضو حداکثر \(lgn\) بار عوض می شود چون در هر مرحله تعداد اعضای دسته ای که نماینده آن عوض می شود دو برابر می شود).
void Union(int x, int y){
    x=Find(x);
    y=Find(y);
    if(x == y)return;
    if(sz[x] < sz[y])swap(x, y);
    sz[x] += sz[y];
    for(int i = 0; i < lst[y].size(); i++){
        int z = lst[y][i];
        Rep[z] = x;
        lst[x].push_back(z);
    }
    lst[y].clear();
}
  • روش دیگری که برای ادغام موجود است برای زمانیست که مجموعه ها را به صورت جنگل در نظر گرفتیم. و در این صورت مانند قسمت بالا می توان با تعداد راس های هر مولفه (مجموعه) مقایسه انجام داد و نماینده مولفه با تعداد راس کمتر را نماینده مولفه دیگر کرد.
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x == y)return;
    if(sz[x] < sz[y])swap(x, y);
    sz[x] += sz[y];
    Par[y] = x;
}

لیست یا جنگل؟

شاید برایتان سوال شود که الان برای اجرای الگوریتم به کدام روش عمل کنیم؟ مجموعه را لیست کنیم یا به شکل گراف دراریم؟ پاسخ سادست اگر دنبال روشی سریع هستید از جنگل استفاده کنید. چرا که هنگامی که از Path Compression استفاده می کنید اردر دو دستور Find و Union به شدت پایین میاد و به \(O(lg^*n)\) می رسد و این یعنی برای \(n = 10^6\) پنج عملیات انجام می شود( \(lg^*n\) به معنی تعداد دفعاتیست که از n، \(lg\) می گیریم تا به یک برسیم، برای مثال \(lg^*4 = 2\) است چون با یک بار لگاریتم گرفتن 4 به 2 تبدیل می شود و با لگاریتم گرفتن دوباره به 1 که در این جریان دو بار لگاریتم گرفتیم پس جواب 2 است). در کل \(lg^*n\) برای \(n\) های کوچک تر از \(2^{65536}\) حداکثر 5 است و این نشان از سریع بودن عملکرد روش Path Compression است.