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

แนวคิด เราจะทำการพิจารณา node ทีละ node สมมติให้กำลังพิจารณาที่ node a แล้วดูว่า node a นั้นมี node อะไรอยู่ใน list ของมันบ้าง ถ้ามี เช่นมี node b อยู่ให้ทำการ เพิ่ม node a ใน list ของ node b แทน และทำการบวกจำนวน node ใน list ของ node b ขึ้นอีกหนึ่ง เมื่อทำแบบนี้จนครบทุก node จะได้ว่าเวลาการทำงานจะเป็น $O(|V|)$ และสำหรับแต่ละ node จะทำการไล่ไปตาม list ของมัน ซึ่งจำนวนของ list ทั้งหมดใน directed graph จะมีเท่ากับจำนวน edge ในกราฟพอดี ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น $O(|V|+|E|)$

จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้