uva11902 dominator

มา dfs กันเถอะ!

โอเค มาเริ่มกันเลย โจทย์ตามนี้

โจทย์

input output

โอเค มาเริ่มกัน

การ travel graph เราจะใช้ dfs กัน โค้ดตามนี้

simple dfs

เอาละ ทีนี้ตามที่โจทย์บอกคือ X จะเป็น dominator ของ Y ถ้าทุกๆเส้นทางจากจุดเริ่มต้นไปยัง Y ต้องผ่านจุด X เสมอ

ดังนั้นถ้าเราเอาจุด X ออกจากกราฟ แล้ว ยังมีเส้นทางจากจุดเริ่มต้นไปยัง Y ได้ แสดงว่า X ไม่ได้เป็น dominator ของ Y นั่นเอง

โอเค มาลองเขียนแบบตรงๆกัน

โดยเราจะ dfs จากจุดเริ่มต้นไปยังจุด Y รอบนึงก่อน จากนั้นเราจะ dfs จากจุดเริ่มต้นไปยังจุด Y อีกรอบ (โดยรอบนี้จะไม่ผ่านจุด X) … ถ้ารอบแรกผ่านจุด Y และรอบที่สองไม่ผ่านจุด Y แสดงว่า X เป็น dominator ของ Y

โอเค code ตามนี้

naive solution

โดยการ dfs มี time complexity O(V²) … ดังนั้น code นี้มี time complexity O(V⁴) ซึ่ง มากเกินนนนน

… เอาละ มา refactor code นี้กันเถอะ โดยเราจะสังเกตุว่าเรามีการ dfs 2 แบบดังนี้

1. แบบแรก กราฟปกติ เพื่อหาว่า ผ่านจุด Y รึเปล่า
2. แบบที่สอง กราฟแบบไม่มีจุด X เพื่อหาว่า ผ่านจุด Y รึเปล่า

ซึ่งในแบบแรก เราสามารถ refactor โดยการ dfs ไปจน complete search รอบเดียว โดยเก็บว่าผ่านจุด 0 … V-1 หรือไม่

ส่วนในแบบที่สอง เราจะทำการวนลูปจาก 0 … V-1 เพื่อวนค่า X จากนั้นเราจะเก็บว่าผ่านจุดเก็บว่าผ่านจุด 0 … V-1 หรือไม่ เช่นกัน

จะได้ code ตามนี้

solution

จะเห็นได้ว่า time complexity ลดเหลือ O(V³) แล้วนั่นเอง

โอเค ข้อนี้ประมาณนี้นะ