https://leetcode.com/problems/satisfiability-of-equality-equations/
https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/234486/JavaC%2B%2BPython-Easy-Union-Find
Approach 1: Connected Components
X. DFS
https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/234491/Simple-Java-DFS-solution-by-building-graph
https://aonecode.com/aplusplus/interviewctrl/getInterview/5478025948892386815
Given an array equations of strings that represent relationships between variables, each string
equations[i] has length 4and 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 <= 500equations[i].length == 4equations[i][0]andequations[i][3]are lowercase lettersequations[i][1]is either'='or'!'equations[i][2]is'='
We have 26 nodes in the graph.
All "==" equations actually represent the connection in the graph.
The connected nodes should be in the same color/union/set.
All "==" equations actually represent the connection in the graph.
The connected nodes should be in the same color/union/set.
Then we check all inequations.
Two inequal nodes should be in the different color/union/set.
Two inequal nodes should be in the different color/union/set.
Explanation
We can solve this problem by DFS or Union Find.
We can solve this problem by DFS or Union Find.
Firt pass all "==" equations.
Union equal letters together
Now we know which letters must equal to the others.
Union equal letters together
Now we know which letters must equal to the others.
Second pass all "!=" inequations,
Check if there are any contradict happens.
Check if there are any contradict happens.
Time Complexity:
Union Find Operation, amortized
First pass all equations,
Second pass all inequations,
Union Find Operation, amortized
O(1)First pass all equations,
O(N)Second pass all inequations,
O(N) int[] uf = new int[26];
public boolean equationsPossible(String[] equations) {
for (int i = 0; i < 26; ++i) uf[i] = i;
for (String e : equations)
if (e.charAt(1) == '=')
uf[find(e.charAt(0) - 'a')] = find(e.charAt(3) - 'a');
for (String e : equations)
if (e.charAt(1) == '!' && find(e.charAt(0) - 'a') == find(e.charAt(3) - 'a'))
return false;
return true;
}
public int find(int x) {
if (x != uf[x]) uf[x] = find(uf[x]);
return uf[x];
}
private int[] parents;
private int circles;
public UnionFind(int n){
parents = new int[n]; // create parent for each node
for(int i=0; i<n; i++){
parents[i] = i; // mark parent of each node as node itself
}
circles = n;
}
public int find(int x){
if(parents[x] == x){
return x;
}
// recur to find parent of this node
return find(parents[x]);
}
public void union(int a, int b){
int groupA = find(a);
int groupB = find(b);
if(groupA != groupB){
parents[groupA] = groupB; // connect as we want to put them in the same circle
circles--; // decrease the group count or the circle count
}
}
}
public boolean equationsPossible(String[] eqns) {
UnionFind u1 = new UnionFind(26);
for(int i=0; i<eqns.length; i++){
if(eqns[i].charAt(1) == '='){
u1.union(eqns[i].charAt(0) - 'a', eqns[i].charAt(3) - 'a');
}
}
for(int i=0; i<eqns.length; i++){
if(eqns[i].charAt(1) == '!'){
int g1 = u1.find(eqns[i].charAt(0) - 'a');
int g2 = u1.find(eqns[i].charAt(3) - 'a');
if(g1 == g2){
return false;
}
}
}
return true;
}Approach 1: Connected Components
All variables that are equal to each other form connected components. For example, if
a=b, b=c, c=dthen a, b, c, d are in the same connected component as they all must be equal to each other.
Algorithm
First, we use a depth first search to color each variable by connected component based on these equality equations.
After coloring these components, we can parse statements of the form
a != b. If two components have the same color, then they must be equal, so if we say they can't be equal then it is impossible to satisfy the equations.
Otherwise, our coloring demonstrates a way to satisfy the equations, and thus the result is true.
public boolean equationsPossible(String[] equations) {
ArrayList<Integer>[] graph = new ArrayList[26];
for (int i = 0; i < 26; ++i)
graph[i] = new ArrayList<>();
for (String eqn: equations) {
if (eqn.charAt(1) == '=') {
int x = eqn.charAt(0) - 'a';
int y = eqn.charAt(3) - 'a';
graph[x].add(y);
graph[y].add(x);
}
}
int[] color = new int[26];
int t = 0;
for (int start = 0; start < 26; ++start) {
if (color[start] == 0) {
t++;
Stack<Integer> stack = new Stack<Integer>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
for (int nei: graph[node]) {
if (color[nei] == 0) {
color[nei] = t;
stack.push(nei);
}
}
}
}
}
for (String eqn: equations) {
if (eqn.charAt(1) == '!') {
int x = eqn.charAt(0) - 'a';
int y = eqn.charAt(3) - 'a';
if (x == y || color[x] != 0 && color[x] == color[y])
return false;
}
}
return true;
}
X. DFS
https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/234491/Simple-Java-DFS-solution-by-building-graph
https://aonecode.com/aplusplus/interviewctrl/getInterview/5478025948892386815
