# A Node Too Far

To avoid the potential problem of network messages (packets) looping around forever inside a network, each message includes a Time To Live (TTL) field. This field contains the number of nodes (stations, computers, etc.) that can retransmit the message, forwarding it along toward its destination, before the message is unceremoniously dropped. Each time a station receives a message it decrements the TTL field by 1. If the destination of the message is the current station, then the TTL field’s value is ignored. However, if the message must be forwarded, and the decremented TTL field contains zero, then the message is not forwarded.

In this problem you are given the description of a number of networks, and for each network you are asked to determine the number of nodes that are not reachable given an initial node and TTL field value.

Problem Source : UVa Online Judge

To solve this problem, we have to implement Graph Searching Technique. The two main approaches are Breadth First Search and Depth First Search. For me, I would use BFS over DFS. This is because my idea is to search all the nodes that can be visited within the TTL field, and count the other nodes that are not visited, that is nodes that cannot be visited within the TTL field. So, we don’t have to go too depth into the graph, but search by layer until it meets the bound of TTL field.

C++

```#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int main() {

int N = 1;

int T;
while (cin >> T && T){

// prepare d
map<int, int> d;

// prepare graphs
vector<vector<int>> graph;
for (int i=0; i<T; i++){
int A, B;
cin >> A >> B;

// check for bounding
if (A >= graph.size()) graph.resize(A+1);
if (B >= graph.size()) graph.resize(B+1);

graph[A].push_back(B);
graph[B].push_back(A);

// -1 for existing node
d[A] = d[B] = -1;
}

// start test cases
int nod, TTL;
while (cin >> nod >> TTL){

if (nod == 0 && TTL == 0) break;

// reset queue;
queue<int> q;

// reset ordinary d
for (int i=0; i<d.size(); i++){
if (d[i] == 1) d[i] = -1;
}

// prepare BFS
q.push(nod);	// initial queue
int i = 0;		// the layer of graph
int key;		// the current node

// start BFS
while (!q.empty() && i <= TTL){

int len = q.size();				// the number of siblings
for (int j=0; j<len; j++){
key = q.front(); q.pop();
if (d[key] != -1) continue;	// explored
else{
d[key] = 1;				// mark as explored

// insert next layer siblings
for (int k=0; k<graph[key].size(); k++){
q.push(graph[key][k]);
}
}
}

i++;
}

int cnt = 0;
for (int i=0; i<d.size(); i++){
if (d[i] == -1) cnt++;
}

cout << cnt << endl;

N++;
}

}

return 0;
}
```

Although the main idea is graph searching, what I learnt most in this problem is not about how to implement BFS, but how to write neat comments. Normally I don’t write comments in my code, but for this problem, when I continued after about an hour of procrastinating, I found that I have to go through every part of it to debug.

After this painful lesson, I think I have a rough idea on the Art of Writing Comments. The rule is simple: not what the code does, but what it is for. For example,

Bad

```d[A] = d[B] = -1;    // let d[A] and d[B] equals to -1
```

Good

```d[A] = d[B] = -1;    // -1 for existing node
```

Can you see the difference between the two comments? Even a new programmer can understand what the code does. However, for others, they might now know what’s the `-1` for. By adding useful comments, we can know that `-1` is to mark existing node. This can be useful for debugging.

Next, let’s see what to do with comments on variables:

```int i = 0;    // the layer of graph
```

I admit that using a easily recognizable variable will be the best move. However, when I need a variable to record the depth of the graph I’m searching in, it’s hard for me to think of one. The variable `layer` is quite lengthy and `lyr` is not even easy to memorize. So, my best choice is simply use the variable `i` and add the comments so that I can easily recall what is it for.

I’m still mastering the art of writing comments. If you have your own tips and tricks, share with me!

Advertisements