Задача: 990. Satisfiability of Equality Equations
Сложность: medium

Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.

Верните true, если возможно назначить целые числа именам переменных таким образом, чтобы удовлетворить всем заданным уравнениям, или false в противном случае.

Пример:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

👨‍💻 Алгоритм:

1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.

2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.

3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.

😎 Решение:

class UnionFind {
    private $parent;

    public function __construct($size) {
        $this->parent = range(0, $size - 1);
    }

    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        if ($rootX != $rootY) {
            $this->parent[$rootX] = $rootY;
        }
    }

    public function connected($x, $y) {
        return $this->find($x) == $this->find($y);
    }
}

class Solution {
    function equationsPossible($equations) {
        $uf = new UnionFind(26);
        
        foreach ($equations as $eq) {
            if ($eq[1] == '=') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                $uf->union($x, $y);
            }
        }
        
        foreach ($equations as $eq) {
            if ($eq[1] == '!') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                if ($uf->connected($x, $y)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний