Satisfiability of Equality Equations Solutions in C++

// Source : https://leetcode.com/problems/satisfiability-of-equality-equations/
// Author : Hao Chen
// Date   : 2019-03-25




class Solution {
private:
    map<char, char>  eq_map; // the table store the equivalent relationship
    void init() {
        for (char ch='a'; ch<='z'; ch++) {
            eq_map[ch] = ch;
        }
    }
public:
    Solution() {
        init();
    }
    
    // find the tail node, 
    // if a == b == c == d, find(a) would return d;
    //                      find(b) would return d;
    char find(char ch) {
        while(ch != eq_map[ch]) {
            ch = eq_map[ch];
        }
        return ch;
    }
    
    //join x equivalent chain with y equivalent chain
    void join(char x, char y) {
        char tx = find(x);
        char ty = find(y);
        if (tx != ty) { 
            eq_map[tx] = ty;
        }
    }

    bool equationsPossible(vector<string>& equations) {
        for (auto e : equations ) {
            if (e[1] == '=' && e[0] != e[3]) { // equal
                join(e[0], e[3]);
            }
        }
        for (auto e : equations) {
            if (e[1] == '!' && (e[0] == e[3] || find(e[0]) == find(e[3]) ) ) { 
                return false;
            }
        }
        return true;
    }
};

/// Source : https://leetcode.com/problems/satisfiability-of-equality-equations/
/// Author : liuyubobobo
/// Time   : 2019-02-13

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// DFS
/// Time Complexity: O(26^2 * n)
/// Space Complexity: O(26^2)
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {

        vector<unordered_set<int>> g(26);
        for(const string& e: equations)
            if(e[1] == '=')
                g[e[0] - 'a'].insert(e[3] - 'a'),
                g[e[3] - 'a'].insert(e[0] - 'a');

        for(const string& e: equations)
            if(e[1] == '!' && isConnected(g, e[0] - 'a', e[3] - 'a'))
                return false;
        return true;
    }

private:
    bool isConnected(const vector<unordered_set<int>>& g, int x, int y){

        vector<bool> visited(26, false);
        return dfs(g, x, y, visited);
    }

    bool dfs(const vector<unordered_set<int>>& g, int s, int t, vector<bool>& visited){

        visited[s] = true;
        if(s == t) return true;
        for(int next: g[s])
            if(!visited[next] && dfs(g, next, t, visited))
                return true;
        return false;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/satisfiability-of-equality-equations/
/// Author : liuyubobobo
/// Time   : 2019-02-09

#include <iostream>
#include <vector>

using namespace std;


/// Using Union-Found
/// Time Complexity: O(n)
/// Space Complexity: O(26)
class UF{

private:
    vector<int> parent;

public:
    UF(int n){
        for(int i = 0 ; i < n ; i ++)
            parent.push_back(i);
    }

    int find(int p){
        if( p != parent[p] )
            parent[p] = find( parent[p] );
        return parent[p];
    }

    bool isConnected(int p , int q){
        return find(p) == find(q);
    }

    void unionElements(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        parent[pRoot] = qRoot;
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {

        UF uf(26);
        for(const string& e: equations)
            if(e[1] == '=')
                uf.unionElements(e[0] - 'a', e[3] - 'a');

        for(const string& e: equations)
            if(e[1] == '!' && uf.isConnected(e[0] - 'a', e[3] - 'a'))
                return false;
        return true;
    }
};


int main() {

    return 0;
}