418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 3

ข้อย่อย 1

แนวคิด สังเกตว่าถ้าเรารัน DFS เราก็จะได้ต้นไม้ที่ได้จากการสำรวจมาหนึ่งต้น ซึ่งจากคุณสมบัติของต้นไม้ จะไม่มี cycle แต่สำหรับข้อนี้กราฟของเราเป็น undirected graph ดังนั้นถ้ามี edge ที่อยู่ในกราฟ แต่ไม่อยู่ในต้นไม้ ก็แสดงว่า edge นั้นเชื่อมระหว่าง node ที่เคยสำรวจไปแล้ว ซึ่งจะได้ว่ามี cycle อยู่ในกราฟนั่นเอง

จากแนวคิดข้างต้น เราก็จะทำการรัน DFS แต่การรันนี้ เราจะแก้ไข code ของ DFS นิดหน่อย โดยในขณะที่มันทำการบอกว่า edge $\{u,v\}\,$ ไหนเป็น edge ในต้นไม้นั้น เราก็จะทำการลบ node $v\,$ ออกจาก list ของ node $u\,$ พร้อมทั้งลบ node $u\,$ ออกจาก list ของ node $v\,$ ด้วย หลังจากการรัน DFS และการกระทำดังกล่าวข้างต้นจบไปแล้ว เราก็สำรวจ node ทีละ node ในกราฟ ถ้า node ไหนยังมี node อื่นอยู่ใน list ของตน แสดงว่า edge ที่เชื่อมระหว่างสอง node นี้ไม่ใช่ edge ในต้นไม้ เราก็จะได้กราฟมี cycle ส่วนวิธีการพิมพ์ cycle ดังกล่าว เราก็ทำการพิมพ์ edge ที่เหลือนี้ก่อน จากนั้นย้อนกลับไปตาม parent ของจุดปลาย node หนึ่งจากสอง node ไปเรื่อย ๆ จนกระทั่ง parent ของ node หนึ่ง ๆ มีค่าเท่ากับ node ปลายข้างนึงของ edge ที่พิมพ์ไปครั้งแรก ก็จะได้ cycle ที่ต้องการ

เขียน pseudocode ตามแนวคิดข้างต้น ได้ดังนี้ <geshi lang="c"> </geshi>

ข้อย่อย 2

อ.วัฒนา