กลุ่มสตริงที่คล้ายกันใน C++

คำอธิบายปัญหา

สตริง X, Y "คล้าย" ถ้าสลับตัวอักษร 2 ตัวใน X ได้ Y (หรือ X==Y) ความคล้ายเป็น equivalence relation หาจำนวนกลุ่ม (connected components) ในลิสต์สตริง A (ทุกคู่เป็น anagram)

ตัวอย่าง

A = ["tars","rats","arts","star"] → Output: 2
Group 1: {tars, rats, arts}, Group 2: {star}

แนวทางแก้ปัญหา: Union-Find (DSU)

1. สร้าง DSU สำหรับ n สตริง
2. ตรวจสอบทุกคู่ (i,j): ถ้า similar → union(i,j)
3. นับจำนวน root ที่แตกต่างกัน

ฟังก์ชัน ok(s1, s2)

นับตำแหน่งที่ s1[i] != s2[i] ถ้า > 2 → false, ไม่เช่นนั้น → true

ตัวอย่างโค้ด C++

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

class Solution {
    vector<int> parent, rank;
    
    int find(int x) { return parent[x]==-1 ? x : parent[x]=find(parent[x]); }
    
    bool unite(int x, int y) {
        int px=find(x), py=find(y);
        if(px==py) return false;
        if(rank[px] >= rank[py]) { rank[px]+=rank[py]; parent[py]=px; }
        else { rank[py]+=rank[px]; parent[px]=py; }
        return true;
    }
    
    bool ok(string& s1, string& s2) {
        int cnt=0;
        for(int i=0; i2) return false;
        return true;
    }
    
public:
    int numSimilarGroups(vector<string>& A) {
        int n = A.size(), ret = n;
        parent.assign(n, -1); rank.assign(n, 1);
        for(int i=0; i