Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

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

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

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


ابزار صفحه