سلام!
امیدواریم که از مسابقه الگوریتمی شماره ۴۲ لذت برده باشید. در ادامه راه‌حل‌های سؤالات مسابقه توضیح داده شدند.
در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات سؤالات و ابهام‌های خود رو مطرح کنید. همچنین اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.
یک گراف ساده‌ی nرأسی حداکثر \frac{n(n-1)}{2} یال دارد.
برخی اشتباهات متداول عبارت‌اند از:
- از چاپ کردن موارد اضافه مثل please enter a number و… پرهیز کنید.
- در زبان پایتون از / به‌جای // برای تقسیم استفاده می‌کنند و جواب به‌صورت اعشاری چاپ می‌شود.
- در زبان‌هایی که برای متغیرها محدودیت وجود دارد، باید از نوع داده
long long int یا long استفاده کنید.
کافی است ماتریس مجاورت را با استفاده از آرایه‌ی دو‌بعدی و دو حلقه‌ی تو‌در‌تو چاپ کنید.
استفاده کردن از ماتریس مجاورت برای حل این سؤال کافی نیست. برای هر رأس مثل v مجموعه N(v) را به این صورت تعریف می‌کنیم: همه رأس‌هایی مثل u، که یال uv در E موجود باشد.
کافی است N(v) را با ساختمان داده‌ای مثل set پیاده‌سازی کنید و با اضافه شدن هر یال مثل uv مجموعه N(v) و N(u) را به‌روزرسانی کنید. با این کار برای فهمیدن وجود یال uv در G (یا G^c) کافی است بررسی کنید که u در N(v) قرار دارد یا نه.
در ابتدا فرض کنید G همبند است. می‌توان ثابت کرد شرط لازم و کافی برای اویلری بودن G این است که درجه‌ی حداکثر دو رأس فرد باشد. منظور از درجه‌ی یک رأس، تعداد یال‌های خارج شده از آن رأس است.
حال شرط اینکه G در صورت ناهمبندی نیز چنین گذری داشته باشد، این است که همه‌ی یال‌های G در یک مؤلفه‌ی همبندی آمده باشند و بقیه‌ی مؤلفه‌ی همبندی‌ها تک‌رأسی باشند.
این مسئله هنوز به صورت چندجمله‌ای حل نشده است. این یک مسئله NP-complete است، اما می‌توانید با استفاده از روش عقب‌گرد بخش زیادی از نمره سؤال و با ترکیب آن با روش meet-in-the-middle کل نمره سؤال را دریافت کنید.
برای به دست آوردن اطلاعات بیشتر این لینک را مطالعه کنید.
شایان ضیایی
