toi

TOI12 weakpoint - กำจัดจุดอ่อน

🏠 รวมเฉลย TOI12

💎 problem.pdf

🎉 solution_topo.cpp

🎉 solution.cpp

Solution

• Detech Cycle ให้ได้ โดยใช้วิธี DFS
• DFS อีกครั้งจากจุดรอบๆ Cycle เพื่อหาขนาดของ sub tree
• ทดลองตัดกราฟโดย
  • ถ้าจุดข้อมูลสำคัญอยู่ในวงกลม
    • ให้ลองตัดลูกๆข้างล่าง
    • ให้ลองตัดจุดอื่นๆรอบ Cycle
  • ถ้าจุดข้อมูลสำคัญอยู่เป็นกิ่ง
    • ให้ลองตัดลูกๆข้างล่าง
    • ให้ลองตัดจุดข้างบน

สามารถ DFS ทีเดียวจากจุดเริ่มแล้ว นับจำนวนที่ตัดได้เลยก็ได้

ในที่นี้ผมใช้เทคนิคแบบ Kahn’s algorithm for Topological Sorting คือการนับ degree ของเส้นเชื่อม โดยอนุมานได้เลยว่า จุดไหนมีเส้นเชื่อม == 1 จะต้องเป็น leaf แน่นอน แล้วก็วนทำไปเรื่อยๆในการกำจัด leaf พร้อมกับได้ขนาดของต้นไม้มาด้วยเลย ทำให้โคดสั้นลงไปอีก