Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:الگوریتم ها:سوال ۷

سوال ۷

گراف جهت‌دار ‎G=(V,E)‎ را در نظر بگیرید که ‎|V|=n‎ و ‎|E|=m‎ است. روی هر یک از رئوس ‎G‎ یک عدد طبیعی بین ‎۱‎ تا ‎n2‎ نوشته شده است. مجموعه‌ی رئوسی که راس ‎v‎ به آن‌ها مسیر جهت‌دار دارد را ‎S(v)‎ می‌نامیم ‎(vS(v))‎. از میان اعداد نوشته شده روی رئوس ‎S(v)‎، کوچک‌ترین عدد را ‎l(v)‎ می‌نامیم. الگوریتمی از ‎O(n+m)‎ بدهید که ‎l(v)‎ را برای تمام رئوس ‎vV‎ حساب کنید.


ابزار صفحه