UVA – 336 – A Node Too Far


#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <queue>
#include <list>
#include <map>

#define N 1000000
using namespace std;
#define MAX 40
int Index = 1;
int bfs(int source, int TTL, bool g[MAX][MAX], int m[]) {

	int distance[MAX];
	memset(distance, -1, sizeof distance);
	distance= 0;

	queue<int> que;
	que.push(source);

	while(!que.empty()){
		int node = que.front();
		que.pop();
		for(int i=1; i<Index; i++)
			if(distance[i] == -1 && g[node][i]){
				que.push(i);
				distance[i] = distance [node]+1;
			}
	}

	int count = 0;
	for(int i=1; i<Index; i++)
		if(distance[i]==-1 || distance[i] > TTL)
			count++;
return count;
}
int main() {

	int E, CASE=1;
	bool g[MAX][MAX];
	int map[N];

	while ((cin >> E)) {
		if (!E)
			break;
		Index =1;
		memset(map, 0, sizeof(map));
		for (int i = 0; i < MAX; i++)
			memset(g[i], 0, sizeof(g[i]));



		while (E--) {
			int a, b;
			cin >> a >> b;

			if (!map[a])
				map[a] = Index++;
			if (!map[b])
				map[b] = Index++;

			g[map[a]][map[b]] = g[map[b]][map[a]] = true;
		}

		int source, TTL;

		while (cin >> source >> TTL) {
			if (!TTL && !source)
				break;

			int co = bfs(map, TTL, g, map);
			printf ("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",CASE++, co, source, TTL);
		}

	}
	return 0;
}

Advertisements

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

%d bloggers like this: