[ UVa ] 336 - A Node Too Far

• গ্রাফ টি সবসময় connected নাও থাকতে পারে । 
• সোর্স নোড টি মূল গ্রাফে নাও থাকতে পারে । সেই ক্ষেত্রে মূল গ্রাফে যতগুলি নোড আছে সেটা প্রিন্ট করতে হবে । 
•  TTL এর মান যত দেয়া থাকবে আমরা গ্রাফ কে ততো লেবেল পর্যন্ত সার্চ করে visited মার্ক করবে । এবং মোট নোড থেকে এই visited নোড কে বিয়োগ করে যেটা পাব সেটায় আমাদের প্রিন্ট করতে হবে । 

কোড :

	/**
	* Problem : 336 - A Node Too Far.
	* Verdict : Accepted.
	* Writer : Mehadi Hasan Menon.
	* Time : 0.060 ms.
	* */
	#include <iostream>
	#include <vector>
	#include <set>
	#include <map>
	#include <queue>
	using namespace std;
	const int mx = 10007;
	set <int> my_set;
	vector<int> graph[mx];
	int bfs(int src, int ttl)
	{
	map <int, bool> vis;
	map <int, int> label;
	// set all the node visited to false.
	for(auto i = my_set.begin(); i != my_set.end(); ++i) {
	vis[*i] = false;
	label[*i] = 0;
	}
	queue <int> Q;
	int total_vis_node = 1;
	Q.push(src);
	vis[src] = true;
	while(!Q.empty())
	{
	int u = Q.front(); Q.pop();
	if(label[u] >= ttl) {
	break; // we can't go through after this label.
	}
	for(int i = 0; i < graph[u].size(); i++)
	{
	int v = graph[u][i];
	if(vis[v] == false)
	{
	label[v] = label[u] + 1;
	vis[v] = true;
	total_vis_node += 1;
	Q.push(v);
	}
	}
	}
	return total_vis_node;
	}
	int main()
	{
	freopen("input.txt", "r+", stdin);
	int nc, tc;
	tc = 1;
	while(scanf("%d", &nc) && nc != 0)
	{
	int x, y;
	for(int i = 0; i < nc; i++)
	{
	scanf("%d %d", &x, &y);
	graph[x].push_back(y);
	graph[y].push_back(x);
	// count total number of nodes in our network.
	my_set.insert(x);
	my_set.insert(y);
	}
	int src, ttl;
	int total_node = my_set.size();
	while(scanf("%d %d", &src, &ttl))
	{
	if(src == 0 && ttl == 0) {
	break;
	}
	int total_vis_node = 0;
	// check the given source is in the graph or not
	if(my_set.find(src) != my_set.end()) {
	total_vis_node = bfs(src, ttl);
	}
	int unreachable_node = total_node - total_vis_node;
	printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", tc++, unreachable_node, src, ttl);
	}
	my_set.clear(); // clear every node form set.
	for(int i = 0; i < mx; i++) {
	graph[i].clear();
	}
	}
	return 0;
	}

view raw 336.cpp hosted with ❤ by GitHub