ক্যাটাগরি : বিএফএস / ডিএফএস ।
প্রবলেম লিঙ্ক : 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; }