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

ข้อ 1

ในชั้นเรียนเราได้พูดถึงการเก็บ undirected graph ด้วย adjacency matrix และ adjacency list

ถ้าเราจะเก็บ directed graph ด้วย adjacency matrix และ adjacency list บ้าง จะต้องเปลี่ยนแปลงรูปแบบการจัดเ็ก็บอย่างไรบ้าง?

ข้อ 2

[Dasgupta, Papadimitriou, Varizari 3.5] กำหนดกราฟแบบมีทิศทาง $G=(V,E)\,$ มาให้ กราฟผันกลับ (reverse) ของ $G\,$ คือกราฟ $G^{R}=(V,E^{R})\,$ โดยที่มีเซตของ vertex เป็นเซตเดียวกันแต่ edge ใน $G^{R}\,$ คือ edge ใน $G\,$ ที่ถูกกลับข้าง (กล่าวคือ $E^{R}=\{(v,u)\ |\ (u,v)\in E\}\,$)

จงออกแบบอัลกอริทึมที่เมื่อให้ $G\,$ ในรูปแบบ adjacency list ให้คำนวณ $G^{R}\,$ ในรูปแบบ adjacency เช่นกัน อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(|V|+|E|)\,$

ข้อ 3

จงออกแบบอัลกอริืทึมที่ตรวจสอบว่ากราฟ $G\,$ ที่ให้มาในรูปแบบ adjacency list มี cycle หรือไม่ ถ้ามีให้พิมพ์ออกมาหนึ่ง cycle (วงไหนก็ได้) อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา $O(n+m)\,$ เมื่อ $n\,$ คือจำนวน vertex $m\,$ คือจำนวน edge