راه‌حل‌های مسابقه الگوریتمی شماره ۴۲ (آموزشی)

1360

سلام!

امیدواریم که از مسابقه الگوریتمی شماره ۴۲ لذت برده باشید. در ادامه راه‌حل‌های سؤالات مسابقه توضیح داده شدند.

در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات سؤالات و ابهام‌های خود رو مطرح کنید. همچنین اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

حداکثر یال گراف

یک گراف ساده‌ی nرأسی حداکثر \frac{n(n-1)}{2} یال دارد.

برخی اشتباهات متداول عبارت‌اند از:

  1. از چاپ کردن موارد اضافه مثل please enter a number و… پرهیز کنید.
  2. در زبان پایتون از / به‌جای // برای تقسیم استفاده می‌کنند و جواب به‌صورت اعشاری چاپ می‌شود.
  3. در زبان‌هایی که برای متغیرها محدودیت وجود دارد، باید از نوع داده ‍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 کل نمره سؤال را دریافت کنید.

برای به دست آوردن اطلاعات بیشتر این لینک را مطالعه کنید.

آموزش برنامه نویسی با کوئرا کالج
امین انوری سرور

اشتراک در
اطلاع از
guest

6 دیدگاه‌
قدیمی‌ترین
تازه‌ترین بیشترین واکنش
بازخورد (Feedback) های اینلاین
View all comments
فاطمه
فاطمه
2 سال قبل

با سلام

در راه حل سوال "گراف مکمل" گفته شده که ماتریس مجاورت باید با set پیاده سازی بشه، گراف مکمل رو با set پیاده سازی کردم ، تست های بیشتری مورد قبول شده ، ولی باز هم خطای Time Limit Exceeded

میده امکانش هست راهنمایی بفرمایید

from collections import defaultdict
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(set())
for i in range(m):
    u,v = map(int,input().split())
    a[u-1].add(v-1)
    a[v-1].add(u-1)
q = int(input())
for i in range(q):
    u,v = map(int,input().split())
    if v-1 in a[u-1]:
        print("NO")
    else:
        print("YES")
سارا
سارا
1 سال قبل

سلام . پاسخ کامل این مجموعه موجود نیست؟

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  سارا

سلام دوست عزیز

راه‌حل‌های این مسابقه به‌صورت کلی توضیح داده شده‌اند

با این حال اگر هنوز هم درمورد سؤالی ابهامی وجود دارد، در قسمت کامنت‌ها سؤالاتتون رو مطرح کنید. سعی می‌کنیم راهنمایی بیشتری کنیم

سارا
سارا
1 سال قبل
پاسخ به  کوئرا بلاگ

ممنون از پاسخگویی شما . ممکن نیست که جوابش به صورت کامل داشته باشم؟ چون مسابقه بالاخره تموم شده :(((

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  سارا

سلام دوست عزیز

این مورد پیگیری میشه با این حال چون زمان زیادی از مسابقه گذشته ممکنه امکان تهیه‌ی راه‌حل‌ها و انتشارش وجود نداشته باشه
در هر صورت شما هر سوال و ابهامی داشته باشید حتما راهنمایی خواهیم کرد