## Sunday, November 30, 2014

### UVa Problem 10243 - Fire! Fire!! Fire!!!

Problem:

Solution:

This is a minimum vertex cover on tree problem. .

For each node v, we wanted to compute two counts. The minimum vertex cover size for the subtree rooted at v, and the minimum vertex cover size for the subtree root at v if v has to be in the cover.

Pick an arbitrary node as root, we have two cases, for leaf and for internal nodes. For leaf, this is easy, if the leaf has a parent, and the parent is in the cover, then the leaf is not in the cover, otherwise the leaf has to be in the cover.

For internal node, there are two possibilities, either it is in the cover or not. If it is in the cover, then all the children node can be free to include itself in the cover or not. Otherwise, all children must be in the cover.

That's the crux of the algorithm, the code is short, dfs is used to determine if the node is a leaf or not, recurrence relation applied on stack unwind.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1184

#include "UVa10243.h"

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

pair<int, int> UVa10243_dfs(int parent, int current, vector<vector<int> >& adjacency_list)
{
vector<pair<int, int> > results;
{
if (*ai != parent)
{
}
}

if (results.size() == 0)
{
// Leaf case
if (parent != -1)
{
return pair<int, int>(0, 1);
}
else
{
return pair<int, int>(1, 1);
}
}
else
{
int free_sum = 0;
int force_sum = 0;
for (vector<pair<int, int> >::iterator ri = results.begin(); ri != results.end(); ri++)
{
free_sum += ri->first;
force_sum += ri->second;
}

int selected_result = 1 + free_sum;
int not_selected_result = force_sum;

return pair<int, int>(min(selected_result, not_selected_result), selected_result);
}
}

int UVa10243()
{
while (true)
{
int number_of_galleries;
cin >> number_of_galleries;
if (number_of_galleries == 0)
{
break;
}
for (int i = 0; i < number_of_galleries; i++)
{
for (int a = 0; a < number_of_adjacent_galleries; a++)
{
}
}

// Step 2: dfs for the answer
pair<int, int> result = UVa10243_dfs(-1, 0, adjacency_list);
cout << result.first << endl;
}

return 0;
}