DSU
============
DSU یا Disjoint-set/Union-find که به آن مجموعه های مجزا هم می گویند یک الگوریتم کاربردی برای مسائل همبندی گراف و همچنین برای محاسبه `MST <https://gtoi.shaazzz.ir/book/11/1.html>`_ است.

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

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

دستور ها
-------------

جستجو (Find)
~~~~~~~~~~~~~

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

- روش اول که برای لیست به کار می رود به این نحو است که فقط کافیست مقدار آرایه :math:`Rep[x]` را برگردانیم.

.. code-block:: cpp

    int Find(int x){
        return Rep[x];
    }

- روش دوم که برای جنگل مورد استفاده قرار می گیرید به این نحو است که باید در هر مرحله از طریق آرایه Par به پدران راس :math:`x` برویم تا به ریشه (نماینده مجموعه) برسیم. 

.. code-block:: cpp

    int Find(int x){
        if (Par[x] == x)
            return x;
        return Find(Par[x]);
    }

ادغام (Union)
~~~~~~~~~~~~~

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

- در ابتدا نماینده این دو عضو را پیدا می کنیم. فرض کنید به ترتیب :math:`X` و :math:`Y` باشند. اگر :math:`X` و :math:`Y` یکی باشند به این معناست که این دو عضو در یک مجموعه هستند و لازم نیست که ادغامی انجام دهیم. اگر برابر نبودند نماینده اعضای مجموعه ای را برابر با نماینده اعضای مجموعه دیگر میکنیم. نکته ای که وجود دارد این است که نماینده مجموعه ای را تغییر می دهیم که تعداد اعضای کمتری دارد، به این دلیل که اردر این عمل :math:`O(n lg(n))` است (نماینده هر عضو حداکثر :math:`lg(n)` بار عوض می شود چون در هر مرحله تعداد اعضای دسته ای که نماینده آن عوض می شود دو برابر می شود). این تکنیک ادغام مجموعه ی کوچکتر در مجموعه ی بزرگتر Union by Rank نام دارد.

.. code-block:: cpp

    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 z : lst[y]){
            Rep[z] = x;
            lst[x].push_back(z);
        }
        lst[y].clear();
    }    

- روش دیگری که برای ادغام موجود است برای زمانیست که مجموعه ها را به صورت جنگل در نظر گرفتیم. و در این صورت مانند قسمت بالا می توان با تعداد راس های هر مولفه (مجموعه) مقایسه انجام داد و نماینده مولفه با تعداد راس کمتر را نماینده مولفه دیگر کرد. در اینصورت برای پیدا کردن ریشه ی مولفه یک راس دلخواه ، حداکثر :math:`lg(n)` بار تابع Find صدا می شود (به زبانی دیگر ارتفاع هر کس در جنگل حداکثر :math:`lg(n)` است).

.. code-block:: cpp

    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)
~~~~~~~~~~~~~
حال اگر از تکنیک فشرده سازی مسیر یا Path Crompression برای پیدا کردن ریشه در تابع Find استفاده کنیم ، می توانیم اردرمان را بهتر کنیم. به این روش که وقتی به دنبال ریشه :math:`x` هستیم در انتها پدر :math:`x` را برابر با ریشه می کنیم. این روش که Path Compression نام دارد باعث می شود تمام راس هایی که در مسیر :math:`x` تا ریشه هستند پدر خود را به ریشه تغییر دهند، در این صورت تعداد بچه های ریشه زیاد می شود. با این روش مسیر :math:`x` به ریشه کوتاه تر می شود (برای درک بهتر این قسمت تابع Find را ببینید) و باعث می شود اردر سرشکن هر عملیات مان :math:`O(lg^*n)` شود. این یعنی برای  :math:`n = 10^6` پنج عملیات انجام می شود (:math:`lg^*n` به معنی  تعداد دفعاتیست که باید از  :math:`n`، لگاریتم بگیریم تا به یک برسیم. برای مثال :math:`lg^*4 = 2` است چون با یک بار لگاریتم گرفتن 4 به 2 تبدیل می شود و با لگاریتم گرفتن دوباره به 1 که در این جریان دو بار لگاریتم گرفتیم پس جواب 2 است). در کل :math:`lg^*n` برای :math:`n` های کوچک تر از :math:`2^{65536}` حداکثر 5 است و این نشان از سریع بودن عملکرد روش Path Compression است.
نکته ای که حائز اهمیت است این است که حتی اگر Path Compression را بدون استفاده از Union by Rank به کار ببریم ، اردر سرشکن هر عملیات مان :math:`O(lg(lg(n)))` خواهد بود و در عمل تفاوتی با استفاده از Union by Rank ندارد!

.. code-block:: cpp

    int Find(int x){
        if(Par[x] != x)
            Par[x] = Find(Par[x]);
        return Par[x];
    }

آندو (Undo)
~~~~~~~~~~~~~
آخرین عملیات ادغام را آندو می کند و دو مجموعه ای که ادغام شده بودند را از هم جدا می کند. فرض کنید که از روش Path Compression استفاده نکنیم. در اینصورت با هر بار صدا شدن تابع ادغام ، تنها دو مقدار :math:`sz_x` و :math:`Par[y]` تغییر می کنند. پس می توانیم تغییراتی که انجام داده ایم را ذخیره کنیم تا در صورت نیاز به آندو ، به آنها رجوع کنیم و مقدار پیشین این دو متغیر را جایگزین مقدار فعلی شان کنیم. بدین شکل می توانیم هر عملیات آندویمان را در :math:`O(1)` پیاده سازی کنیم.

دقت کنید که در صورت داشتن تابع آندو دیگر نمی توانیم از Path Compression استفاده کنیم زیرا دیگر اردرمان خوب  نمی شود (به خاطر بیاورید که اردر Path Compression به صورت سرشکن خوب می شود و هر بار صدا شدن تابع Find به تنهایی ممکن است حتی :math:`O(n)` باشد).

.. code-block:: cpp
    
    int Find(int x){
        if(Par[x] == x)
            return x;
        return Find(Par[x]);
    }
    
    void Union(int x, int y){
        x = Find(x);
        y = Find(y);
        if (x == y)
            return;
        if (sz[x] < sz[y])
            swap(x, y);
        operations.push_back(make_pair(y, sz[y]));
        sz[x] += sz[y];
        Par[y] = x;
    }
    
    void Undo(){
        int y = operations.back().first;
        sz[y] = operations.back().second;
        operations.pop_back();
        int x = Find(y);
        sz[x] -= sz[y];
        Par[y] = y;
    }
   
لیست یا جنگل؟
---------------

شاید برایتان سوال شود که الآن برای اجرای الگوریتم به کدام روش عمل کنیم؟
مجموعه را لیست کنیم یا به شکل گراف دراریم؟
در برخی از مسائل ممکن است نیاز به نگه داشتن مجموعه (مولفه) هر راس و یا امکان آندو کردن عملیات های ادغام پیشین داشته باشیم که در این صورت نیاز به روش لیستی داریم.
در سایر مواقع بهتر است که از روش جنگل استفاده کنیم. چرا که هنگامی که از Path Compression استفاده می کنیم اردر دو دستور Find و Union به شدت پایین میاد و به :math:`O(lg^*n)` می رسد .