Dominator

توسط ابوالفضل مهاجری

ارسال شده در
1396-10-23

Dominator

شرح سوال


سلام

امروز می خایم یک سوال از uvaرو بررسی کنیم و سوالی که برتون در نظر گرفتیم سوال dominator هست.

سوال به ما یک ورودی مثل ورودی زیر به ما میده:

2

5

0 1 1 0 0

0 0 0 1 0

0 0 0 1 0

0 0 0 0 1

0 0 0 0 0

در سطر اول تعداد تست کیسا رو مشخص میکنن (T) و در سطر بعدی تعداد نود ها یا همون گره های گراف مشخص میشه(N) در N سطر بعدی اگر مثلا بین گره i,j یالی بود 1 در غیر این صورت 0 که به معنی عدم وجود یال است.

خب تا این جا ما یک گراف داریم حالا سوال از ما می خاد که اگر راس y توسط راس x دومینیتد(dominated) , کامل پایین توضیح داده شده , شده بود Y در غیر این صورت N  رو به صورت زیر خروجی بدیم:

Case 1:

+--------+

|Y|Y|Y|Y|Y|

+--------+

|N|Y|N|N|N|

+--------+

|N|N|Y|N|N|

+--------+

|N|N|N|Y|Y|

+--------+

|N|N|N|N|Y|

+--------+

خب در سطر اول شماره تست کیس , در خط های بعدی Y و N ها چاپ میشن.

ذکر دو نکته حول این سوال ضروریه که بدونین:

  1. بهترین روش حل سوال استفاده از الگوریتم DFS هست.
  2. دومینیتد(dominated) شدن راس Y توسط راس X در این حالت به وجود میاد که: یک بار DFS میزنیم روی راس 0 اگر در اولین DFS به اون راس رسیدیم و بعد تمام یال های خروجی راس X رو حذف میکنیم اگر در دومین DFS روی راس 0 به راس Y نرسیم راس Y توسط راس X دومینیتد شده است.

می تونین جواب سوال رو دانلود کنین و سوال داشتین در بخش نظرات بپرسین در اسرع وقت جواب میدیم.

تست کیس های بیشتر: دانلود

خروجی تست کیس های بالا: دانلود


توضیحات


سطح سوال لینک سوال
متوسط Dominator

کد حل سوال


حل سوال به زبان:
سی پلاس پلاس java وجود ندارد python وجود ندارد

دانلود حل سوال


PDF

تگ ها:
DFS
شما برای ارسال نظر باید وارد سایت شوید

جستجو در سایت

به کانال تلگرامی ما بپیوندید