Chương trình tìm tổng số nhóm đột biến gen trong C++

Cho danh sách chuỗi genes, mỗi chuỗi cùng độ dài, chỉ chứa ký tự A, C, G, T. Quy tắc nhóm đột biến:

• Hai chuỗi khác nhau đúng 1 ký tự → cùng nhóm.
• Tính chất bắc cầu: s1 với s2 cùng nhóm, s2 với s3 cùng nhóm → s1, s3 cùng nhóm.

Tìm số nhóm đột biến. Ví dụ: ["ACGT","ACGC","ACTT","TTTT","TGTT"] → 2 nhóm: [ACGT,ACGC,ACTT] và [TTTT,TGTT].

Thuật toán (Union-Find / DSU)

• Dùng cấu trúc Union-Find với nén đường dẫn.
• Đối với mỗi gen, thử thay đổi từng vị trí thành A,C,G,T khác, nếu gen mới có trong tập → union.
• Số nhóm = số phần tử gốc ban đầu - số lần union thành công.

Ví dụ triển khai (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), 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) && unite(temp, it)) ret--;
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    vector<string> v = {"ACGT","ACGC","ACTT","TTTT","TGTT"};
    Solution ob;
    cout << ob.solve(v);
    return 0;
}

Đầu vào

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

Đầu ra

2