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

• سوال بعد
• سوال قبل