문제 정의
트리(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 × count_color1입니다. 이분 그래프의 모든 간선은 반드시 두 집합 사이를 연결해야 하기 때문입니다.
- n개의 노드를 가진 트리는 n-1개의 간선을 이미 가지고 있습니다.
- 따라서 최종 답은 count_color0 × count_color1 − (n − 1)입니다.
C++ 구현 예제
#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
이 알고리즘의 시간 복잡도는 트리를 한 번만 순회하므로 O(n)이며, 노드 수가 많은 트리에서도 효율적으로 동작합니다.