[UVa] 336 A Node Too Far.cpp

#include <cstdio>
#include <queue>
#include <map>
#include <vector>
using namespace std;
map<int, int> mapping;
struct node_type{
	vector<int> connceted_node;
};
int NC;
int numOfnode;
int BFS(int start_node, int TTL, node_type node[]);
int main()
{
	//freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d", &NC)) {
		if (!NC) break;

		node_type node[100];
		mapping.clear();

		int node1, node2, i, j;
		for (i=0, j=0; i<NC; ++i) {
			scanf("%d%d", &node1, &node2);
			if (mapping.find(node1) == mapping.end())
				mapping[node1] = j++;
			if (mapping.find(node2) == mapping.end())
				mapping[node2] = j++;
			node[mapping[node1]].connceted_node.push_back(mapping[node2]);
			node[mapping[node2]].connceted_node.push_back(mapping[node1]);
		}
		numOfnode = j;
		int TTL;
		while (scanf("%d%d", &node1, &TTL)) {
			if (!node1 && !TTL) break;
			int numOfNotReach = BFS(node1, TTL, node);
			printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
				   Case++, numOfNotReach, node1, TTL);
		}
	}
	return 0;
}
int BFS(int start_node, int TTL, node_type node[])
{
	queue<int> Q;
	Q.push(mapping[start_node]);
	int visit[100] = {0};
	visit[mapping[start_node]] = 1;

	int nOfReach = 1;
	while (!Q.empty()) {
		int cur = Q.front();
		if (visit[cur] > TTL) return numOfnode - nOfReach;
		Q.pop();
		for (int nxt : node[cur].connceted_node) {
			if(visit[nxt] == 0){
				visit[nxt] = visit[cur] + 1;
				Q.push(nxt);
				++nOfReach;
			}
		}
	}
	return numOfnode - nOfReach;
}