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
A Node Too Far

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s