ধরুন নিচের মতো একটি গ্রাফ আছে। এটি পিটারসন গ্রাফ। ভার্টেক্সগুলো ০ থেকে ৯ পর্যন্ত নম্বর দিয়ে চিহ্নিত। প্রতিটি ভার্টেক্সের কিছু চিঠি আছে। ওই গ্রাফে একটি ওয়াক W বিবেচনা করুন, যেখানে L সংখ্যক ভার্টেক্স ব্যবহার করা হয়েছে। একটি স্ট্রিং S যার L সংখ্যক চিঠি আছে, ওই ওয়াক W দিয়ে রিয়েলাইজ করা হয় যদি W-র চিঠি সিকোয়েন্স এবং S একই হয়। আমরা ভার্টেক্সগুলো একাধিকবার ভিজিট করতে পারি।
উদাহরণস্বরূপ, একটি স্ট্রিং S হলো “ABBECCD”, এটি ওয়াক (0, 1, 6, 9, 7, 2, 3) দিয়ে রিয়েলাইজ করা হয়েছে। আমাদের কাজ হলো এমন একটি ওয়াক খুঁজে বের করা, এবং যদি সেটি থাকে, তবে লেক্সিকোগ্রাফিক্যালি সর্বনিম্ন ওয়াকটি বের করা। যদি এমন কোনো ওয়াক না থাকে, তবে -1 রিটার্ন করা।
অ্যালগরিদম
petersonGraphWalk(S, v) −
শুরু res := শুরুয়ের ভার্টেক্স S-র প্রথম চিঠি বাদে প্রতিটি চিঠি c এর জন্য, do যদি v এবং c-এর মধ্যে আউটার গ্রাফে এজ থাকে, then v := c else if v এবং c+5-এর মধ্যে ইন্ডার গ্রাফে এজ থাকে, then v := c + 5 else return false end if res-এ v যোগ করুন done return true শেষ
উদাহরণ
#include<iostream> using namespace std; bool adj_mat[10][10] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 1, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0} }; char S[100005]; char res[100005]; bool petersonGraphWalk(char* S, int v){ res[0] = v + '0'; for(int i = 1; S[i]; i++){ // আউটার গ্রাফ ট্রাভার্স if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){ v = S[i] - 'A'; } // তারপর ইন্ডার গ্রাফ চেক else if(adj_mat[v][S[i] - 'A' + 5] || adj_mat[S[i] - 'A' + 5][v]){ v = S[i] - 'A' + 5; }else{ return false; } res[i] = v + '0'; } return true; } main() { char* str = "ABBECCD"; if(petersonGraphWalk(str, str[0] - 'A') || petersonGraphWalk(str, str[0] - 'A' + 5)){ cout << res; }else{ cout << -1; } }
আউটপুট
0169723
