در این قسمت دادهساختارهای موجود در کتابخانه استاندارد $C++$ را مرور میکنیم و دادهساختارهای لازم برای پیادهسازی الگوریتمها را معرفی میکنیم.
این دادهساختار همانطور که از نام آن پیداست مجموعهای از تعدادی مجموعهی مجزا است. دو عمل روی این مجموعهها داریم:
مزیت این ساختمان داده زمان کم آن برای عملیات گفتهشده است که $O(\alpha(n))$ است که میتوان در عمل آن را ثابت فرض کرد.
کاربرد این ساختمان داده در الگوریتم کراسکال است.
برای نگهداری گراف از دادهساختارهای زیر میتوان استفاده کرد:
گاهی لازم است قبل از ساخت این ساختمان دادهها، رأسها را به اعداد صحیح $0,…,n-1$ یا $1,…,n$ تصویر کنیم. (با استفاده از تابع $map$). همچنین گاهی لازم است بیشتر از یکی از این دادهساختارها را برای حل یک مسأله بسازیم.
۱-حسن $N\ (1\leq N \leq 100000)$ گاو دارد که خودشان را به صورت «گاوهای همسایه» گروهبندی میکنند. هر گاو در یک مختص یکتا در یک دستگاه مختصات متعامد در چراگاهی است که مختصات $X$ و $Y$ آن در بازه $1…1000000000$ قرار دارد. دو گاو همسایهاند، اگر حداقل یکی از این دو شرط را داشته باشند: ۱) اگر فاصلهی منهتن آنها حداکثر $C\ (1\leq C \leq 1000000000)$ باشد؛ ۲) اگر گاو $A$ و $B$ هر دو همسایهی گاو $Z$ باشند، $A$ همسایهی $B$ هم هست. مختصات گاوها و فاصلهی $C$ داده شده است، تعداد همسایگیها و تعداد گاوها در بزرگترین همسایگی را مشخص کنید.
جواب: فاصله منهتن دو نقطه $(x_1,y_1)$ و $(x_2,y_2)$ برابر $|x_1-x_2|+|y_1-y_2|$ است. به ازای هر گاو یک عنصر در مجموعههای مجزا در نظر میگیریم. اگر دو گاو فاصلهشان در شرط ۱ صدق کند، همسایگی آنها را ادغام میکنیم. شرط ۲ خود به خود به دلیل خاصیت مجموعهای دادهساختار مجموعههای مجزا برقرار میشود. تعداد مجموعهها (=تعداد رأسهای ریشه = تعداد رأسهایی که خودشان پدر خودشان هستند) و بیشینهی تعداد اعضای هر مجموعه را که در آرایهی سایز (برای تشخیص نحوهی ادغام دو مجموعه) نگه داشتیم، برمیگردانیم.
۲-درختی با $N\ (1\leq N \leq 15000)$ رأس داده شده است، گراف کامل (گرافی که بین هر دو رأس آن یک یال است) با کمترین وزن را پیدا کنید که درخت داده شده، درخت پوشای کمینهی منحصر به فرد آن باشد.
جواب: مجموعهی رأسها را در دادهساختار مجموعههای مجزا میگذاریم و مشابه الگوریتم کراسکال، یالهای درخت را اضافه میکنیم و ادغام انجام میدهیم. هر بار که یک یال را با یال دیگری ادغام میکنیم، باید سایر یالهای بین اعضای دو مجموعه از این مقدار بیشتر باشند، بنابراین مقدار آنها را به این مقدار افزایش میدهیم. در پایان چون الگوریتم کراسکال درخت پوشای کمینه را برمیگرداند، جواب تغییری نمیکند. پایان الگوریتم وقتی است که همهی رأسها در یک مجموعه قرار گرفته باشند.
۳- دنبالهی $A$ از $N\ (1\leq N\leq 100000)$ عدد صحیح نامنفی داده شده است. به $Q\ (1\leq Q \leq 100000)$ پرسوجو پاسخ دهید که در هر کدام سه عدد صحیح $v,a,b$ است. جواب تعداد زوج اعداد صحیح $i$ و $j$ است که $1\leq i \leq j \leq N$ و $a\leq j-i+1\leq b$ باشد و به ازای هر عدد صحیح $k$ بین $i$ و $j$ (شامل دو سر بازه) $A[k]\geq v$ باشد.
جواب: راهنمایی: به ازای هر پرسوجو یک دادهساختار مجموعههای مجزا بسازید و بر اساس قیدهای داده شده به آن یال اضافه کنید.