المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:الگوریتم ها:سوال ۶

سوال ۶

یک گراف تهی $n$-رأسی داریم. $q$ درخواست (query) از دو نوع به ما داده می‌شود:

  1. بین دو رأس $u, v$ یک یال اضافه کنیم؛ طوری که دور ایجاد نشود.
  2. فاصله‌ی بین دو رأس $u, v$ را بدهیم (اگر بین دو رأس $u, v$ مسیر وجود نداشت، فاصله‌ی دو رأس $-1$ در نظر گرفته می‌شود).

می‌خواهیم درخواست‌ها را به صورت آنلاین (برخط) پاسخ دهیم. الگوریتمی از $O\big(n\ lg^2(n) + q\ lg(n) \big)$ ارائه دهید؛ طوری که به درخواست‌ها پاسخ دهد.


ابزار صفحه