A Node Too Far – Revisited

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

Below is a slightly efficient version of my previous code.

C++

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

map<int, int> visited;

int main() {
	
	int T;
	while (cin >> T && T){
		
		// prepare adjacency list graph
		map<int, vector<int>> adjList;
		for (int i=0; i<T; i++){
			int A, B;
			cin >> A >> B;
			
			adjList[A].push_back(B);
			adjList[B].push_back(A);
		}
		
		int nod, TTL;
		while (cin >> nod >> TTL && (nod != 0 || TTL != 0)){
			
			visited.clear();
			
			// start standard bfs
			queue<int> q;
			q.push(nod);
			visited[nod] = 0;
			
			while (!q.empty()){
				int x = q.front(); q.pop();
				int size = adjList[x].size();
				for (int i=0; i<size; i++){
					int n = adjList[x][i];
					
					if (visited.count(n)) continue;
					visited[n] = visited[x] + 1;
					q.push(n);
				}
			}
			
			int cnt = 0;
			for (map<int, int>::const_iterator it = visited.begin(); it != visited.end(); it++){
				if ((*it).second > TTL) cnt++;
			}
			
			cnt += adjList.size() - visited.size();
			
			cout << cnt << endl;
			
		}
	}
	
	return 0;
}

We don’t have to check for the bounding like we did when I used vector<vector> graph as our graph data structure. In this code, I used map<int, vector> adjList as my adjacency list data structure so we can simply map an integer and push_back the connecting node.