ক্যাটাগরি : বিএফএস / ডিএফএস ।
প্রবলেম লিঙ্ক : https://uva.onlinejudge.org/external/3/336.html
প্রবলেম : এই প্রবলেমটিতে মূলত বলা হয়েছে, আমাদের কিছু ভার্টেক্স আর তাদের মধ্যে এজ দেয়া থাকবে । আর এগুলো দেয়ার পর আমাদের টেস্ট কেস হিসেবে দেয়া নোড গুলোর মধ্য থেকে কিছু নোড আর তাদের মধ্যের টাইম টু লিভ বা টিটিএল (TTL) দেয়া থাকবে । এই নোড থেকে শুরু করে আমাদের বের করতে হবে টিটিএল এর উপর বেস করে সর্বোচ্চ কয়টা নোড ভিজিট করা যাবে আর কতগুলো যাবে না । যতগুলো যাবে না আমাদের মূলত ঐ সংখ্যাটাই প্রিন্ট করতে হবে । টিটিএল বলতে বুঝিয়েছে আমরা স্টার্টিং নোড থেকে শুরু করে সর্বোচ্চ কতগুলো নোড একটানা ভিজিট করতে পারব বা একই পথে আমরা টানা কয়টা নোড পর্যন্ত যেতে পারব ।
এ প্রবলেমটির মূল অ্যাালগরিদম খুবই সোজা । শুধুমাত্র বিএফএস/লেভেল বাই লেভেল সার্চ করে আমাদের টিটিএল এর নম্বর যত তত লেভেল পর্যন্ত গেলে কতগুলো ভার্টেক্স ভিজিট করতে পারছি আর কতগুলো করতে পারছি না এটা বের করতে পারলেই যথেষ্ট ।
কিন্তু এর মূল সমস্যা হচ্ছে ইনপুটে । এখানে সব আর্বিটারি নোড দেয়া । এগুলোকে গ্রাফে গুছিয়ে স্টোর করাটাই এ প্রবলেম এর সবচাইতে বড় চ্যালেঞ্জ । আমি যেটা করেছিলাম সবগুলো ইনপুট নিয়ে ঐগুলো কে স্ট্রাকচারে রেখেছিলাম যেখানে মোটামুটি ৪টার মত উপাদান ছিল । ২টি হচ্ছে ২টি ভার্টেক্স যেগুলো দেয়া আর বাকি ২টা হচ্ছে আমরা এই ভার্টেক্স গুলোকে আমাদের সুবিধার জন্য কোন নাম দিচ্ছি সেটা । আমি নামটা এভাবে বার করেছিলাম, আমি প্রথমেই দেখেছিলাম আমার ইনপুট এর মধ্যে একদম ভিন্ন নাম্বার কয়টি আছে , সেই নাম্বারটিই নোড কয়টা আছে সেটা বুঝায় । এরপর ছোট থেকে বড়তে সর্ট করেছিলাম আর এদের ইনডেক্স নাম্বরটিকেই এদের নতুন নাম্বার দিয়েছিলাম যেটা নতুনভাবে নোড হিসেবে তাদেরকেই বুঝাবে ।
এভাবে আমি সব আর্বিটারি নোডগুলোকে একটা গুছানো অর্ডারে নিয়ে এসে গ্রাফে স্টোর করেছিলাম । তারপর খুবই সাধারণ ভাবে বিএফএস করে আমাদের আউটপুটটি বের করেছিলাম ।
Code :
আমরা প্রথমে নিজের চেষ্টা করব, নিতান্তই না পারলে নিচের কোডটি দেখে কিছু সাহায্য পেতে পারি ।
#include <bits/stdc++.h>
using namespace std;
vector <int> graph[1000];
int visit[1000];
int levelarr[1000];
struct info
{
int givennode;
int newnode;
} arr[1000];
struct input
{
int one;
int two;
int check;
int real_one;
int real_two;
} pregraph[1000];
bool cmp(int a, int b)
{
if(a < b) return true;
else return false;
}
int bfs(int node, int limit)
{
queue <int> use;
int level = 0,variable,i;
use.push(node);
variable = use.front();
visit[variable] = 1;
levelarr[variable] = 0;
while(use.empty() != 1)
{
variable = use.front();
level = levelarr[variable];
if(level > limit) {
break;
}
for(i = 0; i < graph[variable].size(); i++)
{
int got = graph[variable][i];
if(visit[got] == -1)
{
visit[got] = 1;
levelarr[got] = levelarr[variable] + 1;
use.push(got);
}
}
use.pop();
}
}
int main(void)
{
int edge,i,a,b,j,k,t = 0;
while(scanf("%d",&edge) == 1)
{
if(edge == 0)
{
break;
}
int numarr1[1000],numarr2[1000];
j = -1;
for(i = 1; i <= edge; i++)
{
scanf("%d %d",&a,&b);
pregraph[i].one = a;
pregraph[i].two = b;
pregraph[i].check = 0;
j++;
numarr1[j] = a;
j++;
numarr1[j] = b;
}
sort(numarr1,numarr1+j+1,cmp);
k = -1;
for(i = 0; i <= j; i++)
{
k++;
numarr2[k] = numarr1[i];
while((numarr1[i] == numarr1[i+1]) && (i+1) <= j)
{
i++;
}
}
for(i = 0; i <= k; i++)
{
for(j = 0; j <= edge; j++)
{
if(numarr2[i] == pregraph[j].one)
{
pregraph[j].real_one = i;
}
if(numarr2[i] == pregraph[j].two)
{
pregraph[j].real_two = i;
}
}
}
for(i = 1; i <= edge; i++)
{
int variable1,variable2;
variable1 = pregraph[i].real_one;
variable2 = pregraph[i].real_two;
graph[variable1].push_back(variable2);
graph[variable2].push_back(variable1);
}
int node = k;
int test_node,span,dorkar;
while((scanf("%d %d",&test_node,&span) == 2))
{
if(test_node == 0 && span == 0)
{
break;
}
dorkar = test_node;
for(i = 1; i <= edge; i++)
{
if(pregraph[i].one == test_node)
{
test_node = pregraph[i].real_one;
break;
}
else if(pregraph[i].two == test_node)
{
test_node = pregraph[i].real_two;
break;
}
}
for(i = 0; i < 1000; i++)
{
visit[i] = -1;
levelarr[i] = -1;
}
bfs(test_node,span);
int cnt = 0;
for(i = 0; i <= node;i++) {
if(visit[i] == 1 && levelarr[i] <= span) {
cnt++;
}
}
t++;
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",t,node - cnt + 1,dorkar,span);
}
for(i = 0; i < 1000; i++) {
graph[i].clear();
}
}
return 0;
}