418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 8

สมมติว่า $u\,$ เป็น vertex และให้ $v_{1},v_{2},\ldots ,v_{k}\,$ เป็นลูกของ $u\,$ เราจะได้ว่า

$z[u]=\max(z[v_{1}],z[v_{2}],z[v_{3}],\ldots ,z[v_{k}],x[u])\,$

ฉะนั้นเราสามารถหาค่า $z[u]\,$ สำหรับทุก vertex $u\,$ โดยการปรับปรุง $\mathrm {DFS} \,$ ใหม่ เพื่อให้หลังจาก $\mathrm {DFS} (u)\,$ ทำงานเสร็จแล้ว $z[u]\,$ จะมีค่าถูกต้อง ดังต่อไปนี้

<geshi lang="c"> DFS(u) {

   explored[u] = 1
   z[u] = x[u]
   
   for i = 1 to d[u] do
   {
       v = a[u][i]
       if explored[v] = 0 then
           DFS(v)
       if z[v] > z[u] then
           z[u] = z[v]
   }    

} </geshi>

การหาค่า $z[u]\,$ ของ vertex $u\,$ ทั้งหมดทำได้โดยการรัน $\mathrm {DFS} (r)\,$ ซึ่งทำงานในเวลา $O(|V|+|E|)\,$ ตามต้องการ