المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۵:سوال ۶

Taraneh

اخیرا باستان‌شناسان موفق به کشف یک گنجینه از نامه‌های بسیار قدیمی شده‌اند که به شیوه‌ی پیچیده‌ای رمزگذاری شده‌اند. در انتهای هر نامه یک گراف رسم شده است و کلید رمزگشایی نامه برابر با تعداد تطابق‌های کامل این گراف است. پس از بررسی گراف‌ها مشخص شد که در هر گراف تعدادی از رئوس قرمز و سایر رئوس آبی هستند و رنگ دو سر هر یال متفاوت است. همچنین تعداد رئوس قرمز و آبی برابر است.

با تلاش شبانه‌روزی دانشمندان، الگوریتم متفاوتی برای رمزگشایی نامه‌ها به دست آمد که برای رمزگشایی نامه تنها به باقی‌مانده‌ی کلید نامه بر $4$ نیاز دارد. شما باید به باستان‌شناسان کمک کنید که باقی‌مانده‌ی کلید نامه بر $4$ را محاسبه کنند.

پیاده‌سازی

در این سوال شما باید تابع زیر را پیاده‌سازی کنید.

  • int findKey(int n, int m, int *u, int *v)

این تابع $t$ بار فراخوانی می‌شود. تابع را طوری پیاده‌سازی کنید که با ورودی گرفتن گراف انتهای یک نامه، باقی‌مانده‌ی کلید آن نامه بر $4$ را مشخص کند.

  • $n$: گراف $n$ راس قرمز و $n$ راس آبی دارد. رئوس هر رنگ به طور مجزا با اعداد $0$ تا $n - 1$ شماره‌گذاری شده‌اند.
  • $m$: تعداد یال‌های گراف انتهای نامه
  • $u, v$: دو آرایه به طول $m$. به ازای هر $i$ $(0 \le i \le m - 1)$ یک یال بین راس قرمز با شماره‌ی $u_i$ و راس آبی با شماره‌ی $v_i$ وجود دارد.

ارزیاب نمونه

ارزیاب نمونه ورودی را به صورت زیر می‌خواند: در خط اول عدد $t$، تعداد موارد آزمون آمده است. سپس به ازای هر مورد آزمون، در یک خط دو عدد $n$ و $m$ آمده است. در هر یک از $m$ خط بعد، دو عدد آمده است که عدد خط $i$ ام $u_{i - 1}$ و $v_{i - 1}$ است.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۲۹ نمره): حداقل یکی از مولفه‌های گراف با $C_4$ یک‌ریخت است.
  • زیرمسئله‌ی دوم (۲۹ نمره): حداقل دو راس از یک بخش وجود دارند که مجموعه‌ی رئوس همسایه‌ی آن‌ها یکسان است.
  • زیرمسئله‌ی سوم (۴۲ نمره): بدون محدودیت اضافی.

محدودیت‌ها

  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le t \le 10$
  • $1 \le n \le 50$
  • $0 \le m \le n^2$
  • $0 \le u_i, v_i \le n - 1$
  • گراف یال چندگانه ندارد.

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
1
5 13
0 0
0 1
0 2
0 3
0 4
1 1
1 0
2 2
3 3
3 0
4 0
4 4
2 0
1

ابزار صفحه