Cho mảng equations biểu diễn quan hệ giữa biến, mỗi equations[i] dài 4, dạng "a==b" hoặc "a!=b" (a,b là chữ cái thường). Kiểm tra có thể gán số nguyên cho biến để thỏa mãn tất cả phương trình không.
Ví dụ: ["a==b","b==c","a==c"] → true.
Giải pháp dùng Union-Find (DSU):
Hàm getParent(x, map): tìm gốc với nén đường
Tách equations thành mảng equal và notEqual
Khởi tạo parent[x] = x cho mọi biến xuất hiện
Union các cặp trong equal
Kiểm tra các cặp trong notEqual: nếu cùng gốc → false
Trả về true nếu không mâu thuẫn
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: char getParent(char x, map <char, char> m){ if(m[x] == x) return x; return m[x] = getParent(m[x], m); } bool equationsPossible(vector<string>& e) { vector <int> equal; vector <int> notEqual; map <char, char> parent; int n = e.size(); for(int i = 0; i < n; i++){ parent[e[i][0]]= e[i][0]; parent[e[i][3]]= e[i][3]; if(e[i][1] == '='){ equal.push_back(i); }else{ notEqual.push_back(i); } } for(int i = 0; i < equal.size(); i++){ int idx = equal[i]; char u = e[idx][0]; char v = e[idx][3]; parent[getParent(u, parent)] = parent[getParent(v, parent)]; } for(int i = 0; i < notEqual.size(); i++){ int idx = notEqual[i]; char u = e[idx][0]; char v = e[idx][3]; if(getParent(u, parent) == getParent(v, parent)) return false; } return true; } }; int main(){ vector<string> v1 = {"a==b","b==c","a==c"}; Solution ob; cout << (ob.equationsPossible(v1)); }Đầu vào
["a==b","b==c","a==c"]
Đầu ra
true