online advertising

Sunday, November 30, 2014

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

Problem:

Please find the problem here.

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;
    for (vector<int>::iterator ai = adjacency_list[current].begin(); ai != adjacency_list[current].end(); ai++)
    {
        if (*ai != parent)
        {
            results.push_back(UVa10243_dfs(current, *ai, adjacency_list));
        }
    }

    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)
    {
        // Step 1: Read input
        int number_of_galleries;
        cin >> number_of_galleries;
        if (number_of_galleries == 0)
        {
            break;
        }
        vector<vector<int> > adjacency_list;
        adjacency_list.resize(number_of_galleries);
        for (int i = 0; i < number_of_galleries; i++)
        {
            int number_of_adjacent_galleries;
            cin >> number_of_adjacent_galleries;
            adjacency_list[i].resize(number_of_adjacent_galleries);
            for (int a = 0; a < number_of_adjacent_galleries; a++)
            {
                int adjacent_gallery;
                cin >> adjacent_gallery;
                adjacency_list[i][a] = adjacent_gallery - 1;
            }
        }

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

    return 0;
}

3 comments :

  1. If coloring the tree and calculate the maximum cardinality matching, like a tree that is bipartite, it would be tantamount to calculate the vertex cover. Would not give the solution?

    ReplyDelete
  2. Kőnig's theorem does show that maximum matching = vertex cover for bipartite graph. But I think a one pass DFS is going to be better than the maximum matching algorithm.

    ReplyDelete
    Replies
    1. It is true. But I wanted to test the algorithm for the general case (bipartite graph). But I have not found a problem in which the input is not
      a tree. Finally this problem gives me WA and wanted to know if the method I was using was correct.

      Delete