## Wednesday, September 24, 2014

### UVa Problem 336 - A Node Too Far

Problem:

Solution:

Use breadth first search to find out the set of reachable node with just one minor twist - put the TTL of the message in the queue as well. That allows the message to die out after TTL is reached.

The number of unreachable nodes is than just number of nodes - number of reachable nodes.

The problem might have a lot of queries on the same graph - at this point I am not sure if there exist better algorithm than doing a search on the graph for each query.

What I learnt?

• I should have set the visited flag before I enqueue the item to avoid the item got enqueued twice, I have already made this mistake a million times and still make it. I should not make this mistake ever again.

Code:

#include "stdafx.h"

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

#include "UVa336.h"

#include <iostream>
#include <list>
#include <map>
#include <queue>

using namespace std;

int UVa336()
{

int test_case_id = 1;

while (true)
{
int number_of_edges;
cin >> number_of_edges;
if (number_of_edges == 0)
{
break;
}

// Step 1: Reading the graph and do node number mapping
list<pair<int, int> > edges;
map<int, int> node_number_to_id_map;

// Debug
map<int, int> node_id_to_number_map;

int node_id = 0;
for (int i = 0; i < number_of_edges; i++)
{
int source;
int destination;
cin >> source;
cin >> destination;

edges.push_back(pair<int, int>(source, destination));

map<int, int>::iterator probe1 = node_number_to_id_map.find(source);
if (probe1 == node_number_to_id_map.end())
{
node_number_to_id_map.insert(pair<int, int>(source, node_id++));

// Debug
node_id_to_number_map.insert(pair<int, int>(node_id - 1, source));
}

map<int, int>::iterator probe2 = node_number_to_id_map.find(destination);
if (probe2 == node_number_to_id_map.end())
{
node_number_to_id_map.insert(pair<int, int>(destination, node_id++));

// Debug
node_id_to_number_map.insert(pair<int, int>(node_id - 1, destination));
}
}

// Step 2: Build adjacency lists
int number_of_nodes = node_id;
for (list<pair<int, int> >::iterator ei = edges.begin(); ei != edges.end(); ei++)
{
pair<int, int> rawEdge = *ei;
int source_id = node_number_to_id_map[rawEdge.first];
int destination_id = node_number_to_id_map[rawEdge.second];
}

// Step 3: Process the queries
bool* visited = new bool[number_of_nodes];
while (true)
{
int start_node_number;
int ttl;
cin >> start_node_number;
cin >> ttl;
if (start_node_number == 0 && ttl == 0)
{
break;
}

// The BFS game begins
int start_node_id = node_number_to_id_map[start_node_number];
queue<pair<int, int> > bfs_queue;
bfs_queue.push(pair<int, int>(start_node_id, ttl));
for (int ni = 0; ni < number_of_nodes; ni++)
{
visited[ni] = false;
}
visited[start_node_id] = true;

int reachable_node_count = 0;
while (bfs_queue.size() > 0)
{
pair<int, int> current = bfs_queue.front();
bfs_queue.pop();
int current_node_id = current.first;
int current_ttl = current.second;
reachable_node_count++;
int new_ttl = current_ttl - 1;

// Debug
// cout << "Reaching " << node_id_to_number_map[current_node_id] << " from " << start_node_number << endl;

if (current_ttl > 0)
{
{
int neighbor_node_id = *ni;
if (!visited[neighbor_node_id])
{
visited[neighbor_node_id] = true;
bfs_queue.push(pair<int, int>(neighbor_node_id, new_ttl));
}
}
}
}
cout << "Case " << (test_case_id++) << ": " << (number_of_nodes - reachable_node_count) << " nodes not reachable from node " << start_node_number << " with TTL = " << ttl << "." << endl;
}
delete[] visited;
}