คำอธิบายปัญหา
ต้นไม้ (tree) เสมอเป็นกราฟแบ่งสองส่วน (Bipartite Graph) เนื่องจากเราสามารถแบ่งเป็นสองเซตที่ไม่ซ้อนทับกันด้วยระดับสลับกันได้
กล่าวอีกนัยหนึ่ง เราสามารถระบายสีด้วยสองสีได้ โดยระดับสลับกันจะมีสีเดียวกัน งานคือการคำนวณจำนวนขอบสูงสุดที่สามารถเพิ่มเข้าไปในต้นไม้ได้ เพื่อให้ยังคงเป็นกราฟแบ่งสองส่วน
ตัวอย่าง
ขอบของต้นไม้แสดงในรูปคู่จุดดังนี้:
{1, 2}
{1, 3}
{2, 4}
{3, 5} แล้วเราต้องการเพิ่มอีก 2 ขอบเพื่อให้ยังคงเป็นกราฟแบ่งสองส่วน
- ในการระบายสีกราฟ เซต {1, 4, 5} และ {2, 3} เป็นเซตที่ต่างกัน เนื่องจาก 1 เชื่อมกับ 2 และ 3 ทั้งคู่
- เหลือขอบ 4 และ 5 เนื่องจาก 4 เชื่อมกับ 2 แล้ว และ 5 เชื่อมกับ 3 แล้ว ตัวเลือกที่เหลือคือ {4, 3} และ {5, 2}
อัลกอริทึม
- ทำการ DFS หรือ BFS แบบง่ายๆ ของกราฟและระบายสีด้วยสองสี
- ขณะระบายสี ให้เก็บจำนวนโหนดที่ระบายสีแต่ละสีไว้ ให้จำนวนทั้งสองเป็น count_color0 และ count_color1
- ตอนนี้เรารู้ว่าขอบสูงสุดที่กราฟแบ่งสองส่วนสามารถมีได้คือ count_color0 x count_color1
- เรายังรู้ว่าต้นไม้ที่มี n โหนด มีขอบ n-1 ขอบ
- ดังนั้นคำตอบคือ count_color0 x count_color1 – (n-1)
ตัวอย่างโค้ด
#include <bits/stdc++.h> using namespace std; long long count_color[2]; void dfs(vector<int> graph[], int node, int parent, int color) { ++count_color[color]; for (int i = 0; i < graph[node].size(); ++i) { if (graph[node][i] != parent) { dfs(graph, graph[node][i], node, !color); } } } int getMaxEdges(vector<int> graph[], int n) { dfs(graph, 1, 0, 0); return count_color[0] * count_color[1] - (n - 1); } int main() { int n = 5; vector<int> graph[n + 1]; graph[1].push_back(2); graph[1].push_back(3); graph[2].push_back(4); graph[3].push_back(5); cout << "Maximum edges = " << getMaxEdges(graph, n) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:
Maximum edges = 2
