บทที่ 29 MST และ union-find
จบบทนี้ น้องจะมี union-find ที่รวมกลุ่มและตอบว่าสองคนอยู่กลุ่มเดียวกันไหมได้ในเวลาเกือบคงที่ ใช้นับกลุ่ม หาขนาดกลุ่ม และตรวจว่าเส้นเชื่อมเส้นไหนทำให้เกิดวงจร แล้วใช้มันหา minimum spanning tree ด้วย Kruskal พร้อมเหตุผลว่าทำไม greedy นี้ถึงถูก และหาด้วย Prim ทั้งแบบ priority_queue และแบบ O(N2) สำหรับกราฟที่ทุกคู่มีเส้นถึงกัน ปิดท้ายด้วยรูปแบบที่โจทย์ค่าย 2 และ TOI ชอบซ่อน MST ไว้ เช่น ต่อทุกเมืองให้ถึงกันด้วยต้นทุนน้อยที่สุด มีถนนที่ต้องสร้างแน่นอน มีทางเลือกที่ไม่ใช่เส้นเชื่อม และคำถามเรื่องเส้นที่แย่ที่สุดบนเส้นทาง
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 29.1 union-find | เก็บกลุ่มเป็นต้นไม้ path compression union by size เวลาจริงบนข้อมูลที่ทำให้ต้นไม้ยาว และ recursion ที่พังเมื่อต้นไม้สูงเกินราว 32,000 ชั้นแบบ Code::Blocks ส่วนแบบ -O2 ผ่านที่ 100,000 ชั้นแต่พังที่ 150,000 ชั้น |
| 29.2 นับกลุ่ม ขนาดกลุ่ม และตรวจวงจร | ตอบคำถามแบบออนไลน์ นับกลุ่ม ขนาดกลุ่ม เทียบกับ BFS ทุกคำถาม และหาเส้นที่ปิดวงจรในกราฟไม่มีทิศทาง |
| 29.3 spanning tree และ Kruskal | spanning tree กับ MST Kruskal ด้วยการเรียงกับ union-find และพิสูจน์ด้วย exchange argument |
| 29.4 Prim และเลือกใช้ให้เหมาะกับกราฟ | Prim ด้วย priority_queue Prim แบบ O(N2) สำหรับกราฟหนาแน่น และเลือกระหว่าง Kruskal กับ Prim จากเวลาและหน่วยความจำที่วัดจริง |
| 29.5 โจทย์ที่ซ่อน MST | ดูให้ออกว่าเป็น MST เส้นบังคับ โหนดสมมติ maximum spanning tree และคอขวด |