Satisfiability of Equality Equations ใน C++

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

กำหนดอาร์เรย์สมการรูปแบบ "a==b" หรือ "a!=b" (a,b เป็นตัวอักษรพิมพ์เล็ก) ต้องการทราบว่าสามารถกำหนดค่าจำนวนเต็มให้ตัวแปรแต่ละตัวได้หรือไม่ เพื่อให้สมการทุกสมการเป็นจริง

ตัวอย่าง: ["a==b","b==c","a==c"] → true

วิธีแก้ปัญหา (Union-Find / Disjoint Set Union)

1. สร้าง DSU สำหรับตัวอักษร 26 ตัว
2. ผ่านสมการ "==" ก่อน: union ตัวแปรทั้งคู่
3. ตรวจสอบสมการ "!=": ถ้าตัวแปรทั้งคู่อยู่ในเซตเดียวกัน → false
4. หากผ่านทั้งหมด → true

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

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

class Solution {
public:
    char findParent(char x, unordered_map<char, char>& parent) {
        if(parent[x] == x) return x;
        return parent[x] = findParent(parent[x], parent);
    }
    
    bool equationsPossible(vector<string>& equations) {
        unordered_map<char, char> parent;
        
        // เริ่มต้น parent ของตัวอักษรที่ปรากฏ
        for(auto& eq : equations) {
            parent[eq[0]] = eq[0];
            parent[eq[3]] = eq[3];
        }
        
        // ประมวลผล ==
        for(auto& eq : equations) {
            if(eq[1] == '=' && eq[2] == '=') {
                char u = eq[0], v = eq[3];
                parent[findParent(u, parent)] = findParent(v, parent);
            }
        }
        
        // ตรวจสอบ !=
        for(auto& eq : equations) {
            if(eq[1] == '!' && eq[2] == '=') {
                char u = eq[0], v = eq[3];
                if(findParent(u, parent) == findParent(v, parent))
                    return false;
            }
        }
        return true;
    }
};

int main() {
    vector<string> v1 = {"a==b","b==c","a==c"};
    Solution ob;
    cout << (ob.equationsPossible(v1) ? "true" : "false");
    return 0;
}

อินพุต

["a==b","b==c","a==c"]

เอาต์พุต

true