990.satisfiability-of-equality-equations.cpp

/*
 * @lc app=leetcode id=990 lang=cpp
 *
 * [990] Satisfiability of Equality Equations
 *
 * https://leetcode.com/problems/satisfiability-of-equality-equations/description/
 *
 * algorithms
 * Medium (40.94%)
 * Total Accepted:    9.7K
 * Total Submissions: 23.6K
 * Testcase Example:  '["a==b","b!=a"]'
 *
 * Given an array equations of strings that represent relationships between
 * variables, each string equations[i] has length 4 and takes one of two
 * different forms: "a==b" or "a!=b".  Here, a and b are lowercase letters (not
 * necessarily different) that represent one-letter variable names.
 * 
 * Return true if and only if it is possible to assign integers to variable
 * names so as to satisfy all the given equations.
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: ["a==b","b!=a"]
 * Output: false
 * Explanation: If we assign say, a = 1 and b = 1, then the first equation is
 * satisfied, but not the second.  There is no way to assign the variables to
 * satisfy both equations.
 * 
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: ["b==a","a==b"]
 * Output: true
 * Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
 * 
 * 
 * 
 * Example 3:
 * 
 * 
 * Input: ["a==b","b==c","a==c"]
 * Output: true
 * 
 * 
 * 
 * Example 4:
 * 
 * 
 * Input: ["a==b","b!=c","c==a"]
 * Output: false
 * 
 * 
 * 
 * Example 5:
 * 
 * 
 * Input: ["c==c","b==d","x!=z"]
 * Output: true
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * 1 <= equations.length <= 500
 * equations[i].length == 4
 * equations[i][0] and equations[i][3] are lowercase letters
 * equations[i][1] is either '=' or '!'
 * equations[i][2] is '='
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 */
class Solution {
public:
	int find(int x, vector<int>& parent){
		assert(x>=0 && x<=25);
		if(parent[x] != x)
			return parent[x] = find(parent[x], parent);
		return x;
	}
	void union_(int a, int b, vector<int>& parent){
		int pa = find(a, parent);
		int pb = find(b, parent);
		if(pa != pb)
			parent[pa] = pb;
	}

    bool equationsPossible(vector<string>& equations) {
    	vector<int> parent;
    	for(int i=0; i<26; i++)
    		parent.push_back(i);
    	for(auto const& e: equations)
    		if(e[1] == '=')
    			union_(e[0]-'a', e[3]-'a', parent);
    	
    	for(auto const& e: equations)
    		if(e[1] == '!' && find(e[0]-'a', parent) == find(e[3]-'a', parent))
    			return false;
    			
    	return true;
    }
};