数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中将最大数量的边添加到树中以使其保持二分图
问题陈述
树总是二分图，因为我们总是可以将其分解成两个不相交的集合，并交替设置级别。
换句话说，我们总是用两种颜色对其进行着色，这样交替的级别具有相同的颜色。任务是计算可以添加到树中的最大边数，以使其保持二分图。
示例
树边以顶点对的形式表示如下：
{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
更新于：2020年1月10日
273 次查看
广告