یک الگوریتم کوچک

[Goharshady]

سلام!
یک الگوریتم ساده وجود داره که این مسئله رو حل می کنه:
n نفر وجود دارند که در بین آنها بعضی با هم دشمن هستند. (توجه کنید که دشمنی دو طرفه است).
می خواهیم بدانیم آیا می توان زیرمجموعه ای از این n نفر را پیدا کرد که در آن هر نفر حداقل k دشمن داشته باشد یا خیر

ورودی مسئله:
در ورودی n و k و رابطه بین نفرات داده می شود برای مثال زوج نامرتب {i,j} به این معنی است که i و j با هم دشمن هستند
ورودی در فایل Input.csv قرار می گیرد که شکل آن به این صورت است:
n=4
k=2
{1,2,3},{1,4}
----
خروجی مسئله:
کافیست در فایل Output.txt بنویسید Yes یا No
---
حداکثر حجم فایل exe یک مگابایت است (خیلی زیاده)

 

[mohammad_72]

كل مجموعه رو به صورت يه گراف ذخيره مي‌كنيم هر بار يه راس با درجه‌ي كمتر از k رو حذف مي‌كنيم.
اگه تعداد راسها از k+1 كمتر شد وجود نداره ولي اگه متوقف شد جواب پيدا شده!

مي‌تونيم الگوريتمو بهينه‌تر هم بكنيم مثلا هر دفعه كه راسي رو حذف كرديم به جاي اينكه از اول شروع
كنيم به گشتن دنبال راس با درجه‌ي كمتر از k اول از همسايه‌هاي راسي كه حذف كرديم شروع كنيم.
يا اول راسها رو به ترتيب درجه مرتب كنيم بعد نگاه كنيم كه درجه‌ي راس اول از k كمتره يا نه. اگه نبود كه
حله اگه بود حذفش مي‌كنيم ولي بقيه‌ي راسها رو طوري جابجا مي‌كنيم كه بازم مرتب باشه.
(مطمئن نيستم كه اين روش‌ها واقعا بازدهو بهتر كنه فكر كنم به شيوه‌ي پياده‌سازي برنامه هم ربط داشته باشه)
ممنون از سؤالتون! بازم از اين سؤالا بذاريد!

 

[Goharshady]

با تشکر از شما
شیوه حل مسئله کاملا درست است ولی صرفا به صورت ریاضی مطرح شده است
در این قسمت بیشتر از این که دنبال یک راه حل باشیم دنبال الگوریتمش هستیم.
با این حال جواب خوبی بود.