DSU¶

جستجو (Find)¶

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

• روش اول که برای لیست به کار می رود به این نحو است که فقط کافیست مقدار آرایه \(Rep[x]\) را برگردانیم.

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

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

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

ادغام (Union)¶

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

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

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();
}

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

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

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

آندو (Undo)¶

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

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

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;
}