คำชี้แจงปัญหา
กำหนดจำนวนเต็ม N ซึ่งแทนจำนวนจุดยอด ภารกิจคือการหาจำนวนขอบสูงสุดที่เป็นไปได้ในกราฟสองส่วนของจุดยอด N
กราฟสองส่วน
- กราฟสองส่วนคือกราฟที่มีจุดยอด 2 ชุด
- ชุดมีลักษณะที่จุดยอดในชุดเดียวกันจะไม่มีวันแบ่งขอบระหว่างพวกเขา
ตัวอย่าง
ถ้า N =10 จะมีทั้งหมด 25 ขอบ −
- ทั้งสองชุดจะมีจุดยอด 5 จุด และทุกจุดยอดของชุดแรกจะมีขอบของจุดยอดอื่นๆ ของชุดที่สอง
- ดังนั้นขอบทั้งหมดจะเป็น 5 * 5 =25
อัลกอริทึม
- จำนวนขอบจะสูงสุดเมื่อจุดยอดทุกจุดของชุดที่กำหนดมีขอบของจุดยอดอื่น ๆ ของชุดอื่น เช่น ขอบ =m * n โดยที่ m และ n คือจำนวนขอบในทั้งสองชุด
- เพื่อเพิ่มจำนวนขอบสูงสุด m ต้องเท่ากับหรือใกล้เคียงกับ n มากที่สุด
- ดังนั้น จำนวนขอบสูงสุดสามารถคำนวณได้ด้วยสูตร −
(n * n) / 4
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int getMaxEdges(int n) {
return floor((n * n) / 4);
}
int main() {
int n = 7;
cout << "Maximum edges = " << getMaxEdges(n) << endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Maximum edges = 12
