[ UVa ] 11749 - Poor Trade Advisor.

• আমরা ইনপুট নেয়ার সময়ই max_ppa এর মান বের করবো ।
• এখন ১ নং শহর থেকে যাত্রা শুরু করে n পর্যন্ত সব শহরেই যাব যদি না সেই শহর এ আমরা আগে কখনো গিয়ে থাকি। 
• আমরা কোন একটা শহর থেকে যাত্রা শুরু করলে ওই শহর থেকে যতগুলি শহরে যাওয়া যায় তার সবগুলি তে যাওয়ার জন্য চেষ্টা করবো 
• যদি একটা শহর u থেকে v তে যেতে PPA এর মান max_ppa এর সমান না হয় তবে আমরা সেই রাস্তাটা কে বাদ দিয়ে continue করবো । 
• কোন এটা শহর থেকে যাত্রা শুরু করলে মোট কয়টা শহরে যাওয়া যায় সেটা number_of_city তে জমা করে রাখব । 
• শেষে ম্যাক্সিমাম number_of_city ই হল আমাদের মহান সিজার সাহেবের Provience [ উপনিবেশ ] । যেটা খুজে বের করার জন্য তিনি অস্থির হয়ে গেছেন :P 

 কোড করার আগে :

• আমাদের যদি একই road কয়েক বার ইনপুট দেয় এবং তাদের PPA যদি আলাদা আলাদা হয় যেমন : [ a, b ] = 10,  [ b, a ] = 20,  [ a, b ] = -111 তবে আমাদের কে ম্যাক্সিমাম PPA [ a, b ]=  20 কে নিতে হবে । 
• PPA of that road [ fits in a signed 32 bit variable ] তার মানে PPA কিন্তু নেগেটিভ হতে পারে । তাই max_ppa এর মান শুরুতে -2147483648 দিতে হবে । শূন্য দিলে WA খেতে হবে ;)

কোড :

	/**
	* Problem : 11749 - Poor Trade Advisor.
	* Verdict : Accepted.
	* Writer : Mehadi Hasan Menon.
	* Date : 26.12.16.
	**/
	#include <iostream>
	#include <vector>
	#include <stack>
	#include <algorithm>
	#include <cstdio>
	using namespace std;
	const int mx = 505;
	vector <int> network[mx];
	int road_ppa[mx][mx];
	bool visited[mx];
	int max_ppa;
	int dfs_count_node(int src_node)
	{
	stack <int> si;
	int number_of_city = 1;
	si.push(src_node);
	visited[src_node] = true;
	while(!si.empty())
	{
	int u = si.top();
	si.pop();
	for(int i = 0; i < network[u].size(); i++)
	{
	int v = network[u][i];
	if( road_ppa[u][v] != max_ppa)
	{
	continue; // skip this road :)
	}
	if(visited[v] == false)
	{
	si.push(v);
	visited[v] = true;
	number_of_city += 1;
	}
	}
	}
	return number_of_city;
	}
	int main()
	{
	freopen("input.txt", "r+", stdin);
	int n, m, x, y;
	int ppa;
	while(scanf("%d %d", &n, &m) && n != 0 && m != 0)
	{
	max_ppa = -2147483648;
	for(int i = 1; i <= n; i++)
	{
	for(int j = 1; j <= n; j++)
	{
	road_ppa[i][j] = max_ppa;
	}
	}
	for(int i = 0; i < m; i++)
	{
	scanf("%d %d %d", &x, &y, &ppa);
	network[x].push_back(y);
	network[y].push_back(x);
	road_ppa[x][y] = road_ppa[y][x] = max(road_ppa[x][y], ppa);
	max_ppa = max(max_ppa, ppa);
	}
	int max_number_of_city = 0;
	for(int node = 1; node <= n; node++)
	{
	if(visited[node] == false)
	{
	int new_number_of_city = dfs_count_node(node);
	max_number_of_city = max(max_number_of_city, new_number_of_city);
	}
	}
	printf("%d\n", max_number_of_city);
	for(int i = 1; i <= n; i++)
	{
	visited[i] = false;
	network[i].clear();
	}
	}
	return 0;
	}

view raw 11749.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং :)