Abridged Problem Statement

โจทย์ให้ undirected connected graph ซึ่งมีขนาด $N$ โหนด $M$ เส้นเชื่อม และมีอีก $K$ เส้นเชื่อมที่เรารู้โหนดฝั่งหนึ่งแต่อีกฝั่งจะเป็นอะไรก็ได้ โดยที่หากเราพิจารณา Subgraph ของ $N$ โหนด และ $M$ เส้นเชื่อมที่รู้ปลายทั้งสองฝั่งแล้ว ใน Subgraph จะไม่มี self loop หรือ parallel edge แน่นอน โจทย์ต้องการให้หา Minimum Spanning Tree ของกราฟนี้ โดยที่ให้ระบุด้วยว่าใน M เส้นเชื่อมนี้ใช้เส้นเชื่อมใดบ้าง และใน $K$ เส้นเชื่อมนี้ใช้เส้นเชื่อมใดบ้าง โดยที่ใน $K$ เส้นเชื่อมนี้ให้ระบุปลายอีกฝั่งด้วย

Solution

ในข้อนี้เราจะใช้ Kruskal's Algorithm โดยที่เราจะเรียงลำดับแยกกันระหว่าง $M$ เส้นเชื่อมที่มีทั้ง $2$ ฝั่ง และ $K$ เส้นเชื่อมที่มีฝั่งเดียว และสร้างอาร์เรย์เพื่อเก็บ Disjoint Set และสร้างเซ็ท $S$ ที่เก็บโหนดที่มี parent เป็นตัวเองบนอาร์เรย์ Disjoint Set ซึ่งตอนแรกสุดที่ทุกตัวยัง Disjoint กันอยู่ เราก็จะเก็บทั้ง $N$ โหนดไว้ หลังจากนั้นเราจะทำ Kruskal's Algorithm บนฝั่ง $M$ โดยเลือกหยิบเส้นเชื่อมตามปกติ แต่ว่าก่อนที่จะหยิบเราจะดักไว้ว่า หากเรากำลังพิจารณาเส้นเชื่อมที่ $i$ จาก $M$ เส้นเชื่อมแล้ว หากเส้นเชื่อมนี้เป็นเส้นที่ $j$ บน spanning tree ที่กำลังสร้าง ถ้า $N-j\leq K$ และ weight ของเส้นนี้มีค่ามากกว่า weight ของเส้นเชื่อมที่ $N-j$ จากอาร์เรย์ของเส้นเชื่อมที่มีฝั่งเดียวเมื่อเรียงลำดับจากน้อยไปมาก ให้หยุดขั้นตอนของ Kruskal ทันที แต่หากว่าไม่ตรงเงื่อนไข เราก็จะเลือกเส้นนั้นหากว่าปลายทั้งสองฝั่งบน เส้นเชื่อมอยู่คนละเซ็ทกัน แล้วจึงยูเนียนสองเซ็ทนั้น (เป็ นกระบวนการ Kruskal แบบปกติ) แต่ว่าตอนที่ยูเนียนนั้น เราจะดึงตัวที่ไม่เป็น parent บนเซ็ท ออกจาก $S$ ด้วย หลังจากจบกระบวนการข้างต้นแล้ว เราจะใช้เส้นเชื่อมที่มีปลายข้างเดียวอีก $\left|S\right|-1$ เส้น ซึ่งวิธีการหาว่าจะให้จุดปลายอีกฝั่งเป็นอะไรก็คือ เราจะนำไล่เส้นเชื่อมทีละเส้นจากน้อยไปมาก แล้วให้ปลายอีกฝั่งเป็ นโหนดใดก็ได้ใน $S$ ที่ไม่ใช่ parent ของปลายฝั่งที่ได้รับเข้ามา ด้วยกระบวนการนี้เนื่องจาก $S>1$ ดังนั้นเราจะสามารถลดจำนวน connected component จนเหลือ $1$ ได้เสมอ