C++ এ জিনের মোট মিউটেশন গ্রুপ খুঁজে বের করার প্রোগ্রাম

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map <string, string> parent;
   string getPar(string& a){
      if(parent[a] == a)
         return a;
      return parent[a] = getPar(parent[a]);
   }
   bool unite(string& a, string& b){
      string parA = getPar(a);
      string parB = getPar(b);
      if(parA != parB){
         parent[parA] = parB;
         return true;
      }
      return false;
   }
   bool ok(string &a, string& b){
      int cnt = 0;
      for(int i = 0; i < a.size(); i++){
         cnt += a[i] != b[i];
      }
      return cnt == 1;
   }
   int solve(vector<string> v) {
      sort(v.begin(), v.end());
      set <string> s(v.begin(), v.end());

      int ret = v.size();
      for(auto& it : v){
         parent[it]= it;
      }
      for(auto& it : v){
         for(int j = 0; j < it.size(); j++){
            string temp = it;
            for(char x : {'A', 'C', 'G', 'T'}){
               if(x != it[j]){
                  temp[j] = x;
                  if(s.count(temp)){
                     if(unite(temp, it)) ret--;
                  }
               }
            }
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"};
   Solution(ob);
   cout << ob.solve(v);
}

ইনপুট

{"ACGT", "ACGC", "ACTT", "TTTT", "TGTT"}

আউটপুট

2