คำอธิบายปัญหา
กำหนดจำนวนเต็ม N ซึ่งแทนจำนวนโหนด (Vertices) งานคือการหาจำนวนขอบสูงสุดที่เป็นไปได้ในกราฟแบ่งสองส่วน (Bipartite graph) ที่มี N โหนด
กราฟแบ่งสองส่วน (Bipartite Graph)
- กราฟแบ่งสองส่วนคือกราฟที่มี 2 เซตของโหนด
- เซตเหล่านี้มีลักษณะที่โหนดในเซตเดียวกันจะไม่มีขอบเชื่อมต่อกัน
ตัวอย่าง
ถ้า N = 10 จะมีขอบทั้งหมด 25 ขอบ:
- ทั้งสองเซตจะมีโหนด 5 ตัว และทุกโหนดของเซตแรกจะมีขอบเชื่อมกับทุกโหนดของเซตที่สอง
- ดังนั้น ขอบทั้งหมด = 5 * 5 = 25
อัลกอริทึม
- จำนวนขอบจะสูงสุดเมื่อทุกโหนดของเซตหนึ่งมีขอบเชื่อมกับทุกโหนดของอีกเซต นั่นคือ edges = 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
