12th January 2021

A state is safe, if *__*

the system does not crash due to deadlock occurrence

the system can allocate resources to each process in some order and still avoid a deadlock

the state keeps the system protected and safe

all of the mentioned

**Answer:** the system can allocate resources to each process in some order and still avoid a deadlock

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: falseExplanation: 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: trueExplanation: We could assign a = 1 and b = 1 to satisfy both equations.Example 3:â€‹Input: ["a==b","b==c","a==c"]Output: trueExample 4:â€‹Input: ["a==b","b!=c","c==a"]Output: falseExample 5:â€‹Input: ["c==c","b==d","x!=z"]Output: true

*First, going through equality equations and use the union operation to join the variables in one set.*

*Second, going through inequality equations and verify that the variables are not in the same set using the find operation.*

*In the end, there are two sets [a, c, d, f] and [b, e, g].*

int uf_find(vector<int> &uf, int i) {return uf[i] == -1 || uf[i] == i ? i : uf_find(uf, uf[i]);}bool equationsPossible(vector<string>& equations) {vector<int> uf('z' + 1, -1);for (auto s : equations)if (s[1] == '=') uf[uf_find(uf, s[0])] = uf_find(uf, s[3]);for (auto s : equations)if (s[1] == '!' && uf_find(uf, s[0]) == uf_find(uf, s[3])) return false;return true;}