Course4all
Join us on telegram
Home/dsa/Union Find/Satisfiability of Equality Equations

Satisfiability of Equality Equations

Master this topic with zero to advance depth.

Satisfiability of Equality Equations

Given equations like 'a==b' or 'b!=a', check if it's possible to satisfy all equations.

Medium

Examples

Input: ["a==b","b!=a"]
Output: false
Approach 1

Level III: Union-Find (Double Pass)

Intuition

Pass 1: Process all '==' and union symbols into components. Pass 2: Process all '!=' and check if the symbols already share a root. If they do, it's a contradiction.

⏱ O(N \cdot \alpha(26))💾 O(26)

Detailed Dry Run

a==b (Union a,b). b==c (Union b,c). a!=c (Find a=c, Find c=c. Conflict!).

java
class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] p = new int[26]; for(int i=0; i<26; i++) p[i]=i;
        for(String e:equations) if(e.charAt(1)=='=') p[find(p, e.charAt(0)-'a')] = find(p, e.charAt(3)-'a');
        for(String e:equations) if(e.charAt(1)=='!' && find(p, e.charAt(0)-'a') == find(p, e.charAt(3)-'a')) return false;
        return true;
    }
    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }
}
← Previous QuestionNumber of Connected Components
Next Question →Most Stones Removed