418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 7

สังเกตได้ว่า cycle ที่มีความยาวเป็น 4 นั้น ถ้าพิจารณาอีกมุมหนึ่งก็คือ vertex 4 vertex ที่มี edge เชื่อมจาก vertex ที่หนึ่งไป vertex ที่สอง จาก vertex ที่สองไป vertex ที่สาม จาก vertex ที่สามไป vertex ที่สี่ และจาก vertex ที่ 4 ไป vertex ที่หนึ่งนั่นเอง ดังนั้นถ้าเราใช้เทคนิคแบบ brute force เราจะได้ว่า วัตถุที่เราต้องการค้นหาคือ vertex 4 vertex จากทั้งหมด $n\,$ vertex ที่มีเงื่อนไขข้างต้นนั่นเอง ดังนั้นเวลาการทำงานของอัลกอริทึมแบบ brute force นี้จะเป็น ${n \choose 4}=O(n^{4})\,$ นั่นเอง แต่เนื่องจากโจทย์ข้อนี้ต้องการให้ได้เวลาการทำงานเป็น $O(n^{3})\,$ ดังนั้น อัลกอริทึมข้างต้นจึงใช้ไม่ได้

เราจะใช้อัลกอริทึมต่อไปนี้แทน