เราสามารถมองปัญหานี้เป็น Directed Graph ได้ดังนี้
- พรรคการเมืองแต่ละพรรค เป็น node (หลังจากนี้ จะขอเรียก node ของพรรค x ว่า เฉยๆ)
- หากมีข้อมูลระบุว่า พรรค มีคะแนน น้อยกว่า พรรค ให้สร้างเส้นเชื่อมที่มีทิศทางจาก ไปยัง
- ในทางตรงกันข้าม หากมีข้อมูลระบุว่า พรรค มีคะแนน มากกว่า พรรค ให้สร้างเส้นเชื่อมที่มีทิศทางจาก ไปยัง
- หากมีข้อมูลระบุว่า พรรค มีคะแนน เท่ากับ พรรค ให้เราสร้าง ใหม่ขึ้นมา ขอเรียกโหนดนั้นว่า และให้
- เปลี่ยนทิศทาง ของ เส้นเชื่อมที่ชี้มายัง หรือ ทั้งหมด ให้ชี้มายัง แทน
- ในทำนองเดียวกัน เส้นเชื่อมที่ชี้ออกจาก หรือ ทั้งหมด ให้มาชี้ออกจาก แทน
- กล่าวได้ว่า เราทำการผสานโหนด และ เป็นโหนดเดียวกันนั่นเอง
จะได้ว่า โจทย์ข้อนี้ก็คือปัญหา Topological Sorting สุดคลาสสิกนั่นเอง
ในการ implement เราสามารถใช้เทคนิค Sack เข้ามาช่วยในการผสานโหนดได้อย่างมีประสิทธิภาพ
แต่มีวิธีที่เรียบง่ายกว่าคือ การทำแบบ off-line โดยรับข้อมูลเข้ามาทั้งหมดก่อน แล้วทำการผสานโหนดที่คะแนนเท่ากันด้วย Disjoint Set Union แล้วจึงค่อยทำการสร้างเส้นเชื่อมนั่นเอง
Time Complexity : โดยที่ คือ Inverse Ackermann Function
Space Complexity :