معلم علی برای برای یک مسابقه یال‌های گرافی همبند با $n$ راس و $e$ یال را با شماره‌های $1$ تا $e$ شماره‌گذاری کرده است. او به هر راس نیز یک شماره $c_i$ نسبت داده است که $c_i$ برابر کمینه عدد یال‌های مجاور راس $i$ می‌باشد. معلم یال‌های گراف به همراه $c_i$ ها را به بچه‌ها داده است. برنده مسابقه کسی است که یال‌های گراف را طوری شماره‌گذاری کند که با شرایط فوق همخوانی داشته باشد و هم‌چنین وزن درخت پوشای کمینه آن از همه کمتر باشد. الگوریتمی از $Ο(n \log n+e)$ ارائه دهید که در این امر علی را یاری کند.

• سوال قبل