คำชี้แจงปัญหา
ต้นไม้มักจะเป็นกราฟสองส่วน เนื่องจากเราสามารถแบ่งออกเป็นชุดที่ไม่ปะติดปะต่อกันด้วยระดับอื่นได้
กล่าวอีกนัยหนึ่งเราระบายสีด้วยสองสีเสมอเพื่อให้ระดับอื่นมีสีเดียวกัน งานคือการคำนวณจำนวนสูงสุด ของขอบที่สามารถเพิ่มลงในแผนภูมิเพื่อให้ยังคงเป็นกราฟแบบสองส่วน
ตัวอย่าง
ขอบต้นไม้แสดงคู่จุดยอดดังนี้ -
{1/}
{1/}
{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
