문제 설명
짝수 개의 꼭짓점이 있는 무방향 트리가 주어지면 결과 포리스트의 연결된 각 구성 요소가 짝수의 꼭짓점을 갖도록 이 트리에서 최대 가장자리 수를 제거해야 합니다.
예시
위에 표시된 트리에서 빨간색으로 표시된 최대 2개의 가장자리 0-2 및 0-4를 제거하여 연결된 각 구성 요소가 짝수의 정점을 갖도록 할 수 있습니다.
알고리즘
- 트리가 연결될 때 시작 노드에서 DFS 수행
- 현재 노드 아래에 있는 하위 트리의 노드 수를 0으로 초기화
- 현재 노드의 모든 하위 트리에 대해 재귀적으로 다음을 수행합니다. -
- 현재 하위 트리의 크기가 짝수이면 하위 트리 연결을 끊을 수 있으므로 결과를 1 증가시킵니다.
- 또는 현재 하위 트리의 노드 수를 현재 수에 추가
예시
이제 예를 살펴보겠습니다 -
#include <bits/stdc++.h>
using namespace std;
int dfs(vector<int> g[], int u, bool visit[], int& res) {
visit[u] = true;
int currComponentNode = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!visit[v]) {
int subtreeNodeCount = dfs(g, v, visit, res);
if (subtreeNodeCount % 2 == 0)
res++;
else
currComponentNode += subtreeNodeCount;
}
}
return (currComponentNode + 1);
}
int maxEdgeRemovalToMakeForestEven(vector<int> g[], int N) {
bool visit[N + 1];
for (int i = 0; i <= N; i++)
visit[i] = false;
int res = 0;
dfs(g, 0, visit, res);
return res;
}
void addEdge(vector<int> g[], int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
int main() {
int edges[][2] = {{0, 2}, {0, 1}, {0, 4}, {2, 3}, {4, 5}, {5, 6}, {5, 7} };
int N = sizeof(edges)/sizeof(edges[0]); vector<int> g[N + 1];
for (int i = 0; i < N; i++)
addEdge(g, edges[i][0], edges[i][1]);
cout << "Answer = " << maxEdgeRemovalToMakeForestEven(g, N) << endl;
return 0;
} 출력
Answer = 2