C++-এ শব্দগুলোর সর্টেড অর্ডার যেন হয় এমন বর্ণমালার ক্রম নির্ণয়

শব্দের একটি অ্যারে দেওয়া আছে। ইংরেজি বর্ণমালার যেকোনো ক্রম খুঁজে বের করুন যাতে শব্দগুলো आरোহী ক্রমে সর্টেড মনে হয়। না পেলে "impossible" ফেরত দিন।

ইনপুট: ["efgh","wxyz"] -> আউটপুট: "zyxvutsrqponmlkjihgfewdcba"

সমাধানের ধাপসমূহ

• ALPHABET=26। n=শব্দের সংখ্যা।
• এডজেসেন্সি লিস্ট (adj) এবং ইন-ডিগ্রি (in) অ্যারে তৈরি করুন।
• পারwise শব্দ তুলনা করুন: প্রথম ভিন্ন অক্ষর পেলে প্রথمَ অক্ষর দ্বিতীয় অক্ষরের আগে আসবে এমন ডিরেক্টেড এজ যোগ করুন।
• টপোলজিক্যাল সর্ট (Kahn's algorithm) দিয়ে অর্ডার বের করুন। সাইকেল থাকলে "Impossible"।

উদাহরণ (C++ কোড)

#include <bits/stdc++.h>
using namespace std;
#define ALPHABET 26

void search_ordering(vector v) {
    int n=v.size();
    if(n==1) { cout<<"abcdefghijklmnopqrstuvwxyz"; return; }
    vector adj[ALPHABET], in(ALPHABET,0);
    string pre=v[0];
    for(int i=1;is.size()) { cout<<"Impossible"; return; }
        pre=s;
    }
    stack st;
    for(int i=0;i out; bool vis[26]={0};
    while(!st.empty()) {
        int x=st.top(); st.pop();
        vis[x]=true; out.push_back(x+'a');
        for(int y:adj[x]) if(!vis[y]) { in[y]--; if(in[y]==0) st.push(y); }
    }
    for(int i=0;i v={"efgh","wxyz"};
    search_ordering(v);
}

ইনপুট

{"efgh","wxyz"}

আউটপুট

zyxvutsrqponmlkjihgfewdcba