สมมติว่าเราได้รับกราฟและขอให้ค้นหาขนาดต่ำสุดของกลุ่มที่ใหญ่ที่สุดในกราฟ กลุ่มของกราฟเป็นส่วนย่อยของกราฟที่จุดยอดทุกคู่อยู่ติดกัน นั่นคือ มีขอบอยู่ระหว่างจุดยอดทุกคู่ การหากลุ่มที่ใหญ่ที่สุดในกราฟเป็นไปไม่ได้ในช่วงเวลาพหุนาม ดังนั้นเมื่อพิจารณาจากจำนวนโหนดและขอบของกราฟขนาดเล็ก เราจะต้องค้นหากลุ่มที่ใหญ่ที่สุดในนั้น
ดังนั้น ถ้าอินพุตเหมือนโหนด =4 ขอบ =4; แล้วผลลัพธ์จะเป็น 2
ในกราฟด้านบน ขนาดสูงสุดของกลุ่มคือ 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน helper() นี่จะใช้เวลา x, y
- ga:=x mod y
- gb :=y - กา
- sa :=ผลหารของมูลค่าของ (x / y) + 1
- sb :=ผลหารของมูลค่าของ (x / y)
- คืนค่า ga * gb * sa * sb + ga *(ga - 1) * sa * sa / 2 + gb * (gb - 1) * sb * sb / 2
- ผม :=1
- j :=โหนด + 1
- ในขณะที่ i + 1
- p :=i + ค่าพื้นของ ((j - i) / 2)
- k :=helper(nodes, p)
- ถ้า k <ขอบ แล้ว
- ผม :=พี
- มิฉะนั้น
- j :=p
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
import math def helper(x, y): ga = x % y gb = y - ga sa = x // y + 1 sb = x // y return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2 def solve(nodes, edges): i = 1 j = nodes + 1 while i + 1 < j: p = i + (j - i) // 2 k = helper(nodes, p) if k < edges: i = p else: j = p return j print(solve(4, 4))
อินพุต
4,4
ผลลัพธ์
2
