Blind Ballot

o62_mar_c2_blind

เราสามารถมองปัญหานี้เป็น Directed Graph ได้ดังนี้

  1. พรรคการเมืองแต่ละพรรค เป็น node (หลังจากนี้ จะขอเรียก node ของพรรค x ว่า xx เฉยๆ)
  2. หากมีข้อมูลระบุว่า พรรค aa มีคะแนน น้อยกว่า พรรค bb ให้สร้างเส้นเชื่อมที่มีทิศทางจาก aa ไปยัง bb
  3. ในทางตรงกันข้าม หากมีข้อมูลระบุว่า พรรค aa มีคะแนน มากกว่า พรรค bb ให้สร้างเส้นเชื่อมที่มีทิศทางจาก bb ไปยัง aa
  4. หากมีข้อมูลระบุว่า พรรค aa มีคะแนน เท่ากับ พรรค bb ให้เราสร้าง nodenode ใหม่ขึ้นมา ขอเรียกโหนดนั้นว่า (a,b)(a,b) และให้
    • เปลี่ยนทิศทาง ของ เส้นเชื่อมที่ชี้มายัง aa หรือ bb ทั้งหมด ให้ชี้มายัง (a,b)(a,b) แทน
    • ในทำนองเดียวกัน เส้นเชื่อมที่ชี้ออกจาก aa หรือ bb ทั้งหมด ให้มาชี้ออกจาก (a,b)(a,b) แทน
    • กล่าวได้ว่า เราทำการผสานโหนด aa และ bb เป็นโหนดเดียวกันนั่นเอง

รูปที่1

จะได้ว่า โจทย์ข้อนี้ก็คือปัญหา Topological Sorting สุดคลาสสิกนั่นเอง

ในการ implement เราสามารถใช้เทคนิค Sack เข้ามาช่วยในการผสานโหนดได้อย่างมีประสิทธิภาพ
แต่มีวิธีที่เรียบง่ายกว่าคือ การทำแบบ off-line โดยรับข้อมูลเข้ามาทั้งหมดก่อน แล้วทำการผสานโหนดที่คะแนนเท่ากันด้วย Disjoint Set Union แล้วจึงค่อยทำการสร้างเส้นเชื่อมนั่นเอง

Time Complexity : O(Mα(n))\mathcal{O}(M*\alpha(n)) โดยที่ α(n)\alpha(n) คือ Inverse Ackermann Function
Space Complexity : O(N+M)\mathcal{O}(N+M)