المپدیا

یال دلخواهی را در نظر بگیرید که ابتدا بین دو راس با برچسب‌های $\{a\}$ و $\{b\}$ قرار داشته باشد. با انجام چند عملیات، این یال به چه صورت تغییر وضعیت می‌دهد؟

اگر یالی بین دو راس با برچسب‌های $\{a\}$ و $\{b\}$ باشد، یال همواره بین دو راس خواهد بود که در مجموعه‌ی یک راس برچسب عضو $a$ و در مجموعه‌ی دیگری عضو $b$ باشد. اگر $a$ و $b$ در یک مجموعه باشند چه رخ می‌دهد؟

حال می‌بایست در $O(n)$ بررسی کنیم به ازای هر دو عنصر $a$ و $b$ ای که در دور ابتدایی مجاور هستند، در گراف نهایی نیز یالی میان راس‌هایشان باشد. این کار به ازای هر کدام از این دو عدد در چه اردری قابل اجرا است؟

اگر به ازای هر دو عنصر $a$ و $b$ مجموعه‌های نهایی آن‌ها را بر حسب ورودی ذخیره کنیم و از تعداد یال‌هایی که به هر یک از رئوس آن‌ها متصل است یک واحد کم کنیم، در چه صورتی پس از اجرای کامل الگوریتم گراف ساخته شده می‌تواند از اعمال مورد نظر بدست آید؟