کد

ایده‌ی اصلی اینه که یه گراف جدید بسازین و هر راس رو یه جفت راس (v,u) توی گراف اصلی قرار بدین. دو تا راس مثل‌‌ ‌‌ ‌ ‌ ‌ ‌ ‌ (v,u) , (x,y) رو به هم وصل کنید اگر و تنها اگر وقتی که نفر اول در راس v قرار داره و نفر دوم در راس u می‌تونن در حرکت بعدی به ترتیب در x و y باشند. خب حالا اگه از راس (v,u) تو گراف dfs بزنیم می‌تونیم بفهمیم که آیا می‌شه از (v,u) به (u,v) رفت یا نه که این همون جواب ماست.

ولی یه مشکلی هست اونم اینه که این گرافی که ما می‌سازیم تعداد یال‌های زیادی داره(فک کنم از اردر n^4) که خیلی بده برای dfs پس اینجاس که یه ایده‌ی خیلی قشنگ می‌زنیم تا تعداد یال‌های گراف رو کم کنیم. اون ایده اینه:

فک کنید که توی هر حرکت اول نفر اول حرکت می‌کنه بعد نفر دوم. پس اگه بتونیم به حالتی که نفر اول توی u و نفر دوم توی v هست و الان نوبت نفر اول هست برسیم جواب yes هست و در غیر این صورت جواب no می‌شه. اگه به جای اینکه راس‌های گراف رو دوتایی‌های مرتب درنظر بگیریم سه‌تایی مرتب در نظر بگیریم به این صورت که (v,u,s) یعنی اینکه نفر اول توی راس v و نفر دوم توی u هست و الان نوبت نفر sـام هست تعداد یال‌های گرافمون از اردر n^۳ می‌شه. چون از هر راس (v,u,s) حداکثر به ‌ ‌ ‌ n-1 راس دیگه یال داریم پس تعداد کل یال‌ها از اردر n^3 بیشتر است که خب با وضعیت سوال خیلی خوبه.(یه چیزی حدود 8^10 می‌شه که معمولن جاج‌های آنلاین به قدری قوی هستن که بتونن در کمتر از یه ثانیه کار رو انجام بدن) (در ضمن این سوال تایمش فک کنم ۳ ثانیه باشه)

گراف جدید همه‌ی خاصیت های مورد نیاز ما رو داره و می‌تونیم ازش یه dfs بزنیم و جواب سوال رو به دست بیاریم

پ.ن

اگه سوال این بود که کمترین زمان مورد نیاز برای چنین عملی رو بدین می‌شه با استفاده از bfs روی گرافی که می‌سازیم کوتاه‌ترین فاصله بین رئوس (v,u,1) و (u,v,1) رو پیدا کنیم و نصفش رو به عنوان جواب برگردونیم. :)

(در حالت معمولی هم اگر به جای dfs از bfs استفاده کنیم ضریب کمتری می‌خوره و تایم نخواهد شد ولی همین راه هم مشکلی نداره)

اگه مشکلی توی فهم راه حل بود در نظرات بگید :)

پ.ن

کد به دلیل یه باگ کوچیک عوض شد.

سلام

پرواضح : هرجای مسئله که ما بتونیم جای این دو نفر رو عوض کنیم حله دیگه چون هرطوری که تاالان اومده بودن به این موقعیت به هم دیگه بگن که حالا هرکدوم جای اونیکی برگرده :)

حالا ادعا میکنم اگه گرف دور داشته باشه حله !!

اول اینکه میتونن همزمان توی دور باشن ! فرض کنید هر دو همزمان به سمت دور خاصی راه بیافتند اونیکه اول رسید چون طول دور حداقل سه هستش بره روی اون یالی که نفر دیگه نمیخواد رو راساش قرار بگیره !(رفتن رو یال یعنی رو دو سرش هی بره اینور هی بره اونور )

پس الان هردو همزمان رویه یه دورن !

حالا اگه از یه طرف دور تعداد راسهای بین زوج باشه اون دو نفر راحت جاشونو عوض میکنن ! چون همدیگر رو نخواهند دید(دیدن رو راس انجام میگیرد نه رو یال)

حالا اگه از دو طرف فرد باشه هر دو پاد ساعتگرد حرکت کنند اولین نفری که رسید به راس اونیکی اونجا رو یالش بره و تا اونیکی برسه به راس این یارو (چون از هر دو طرف فرده زمانی هست که این دو نفر جاشون عوض میشه ) پس کلا حله !

تو درختم اگه طول مسیر بینشون زوج باشه که حله ! و اگرنه درخت نباید هزار پا باشه (به طوریه که مسیر بین u,v جزو ستون فقرات باشه )!!( یه ذره واضحهو اگه دوست داشتین اینجاشم میگم )

اگه باگ زدم بگید ! :)