문제 설명
트리는 항상 두 개의 분리된 집합으로 나눌 수 있으므로 항상 이분 그래프입니다.
즉, 대체 레벨이 동일한 색상을 갖도록 항상 두 가지 색상으로 색상을 지정합니다. 작업은 최대 번호를 계산하는 것입니다. 이분 그래프를 유지하기 위해 트리에 추가할 수 있는 가장자리의 수입니다.
예시
트리 에지는 다음과 같이 꼭짓점 쌍으로 표현됩니다. -
{1, 2}
{1, 3}
{2, 4}
{3, 5} 그런 다음 Bipartite Graph를 유지하려면 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