Check Equations

In this approach, we will make a graph out of equations, we will add an edge between two nodes if there exists and the ‘==’ sign between them. This will make all the equal elements in the same components of the graph and all the unequal in different components.

The for each equation we have a ‘!=’ between nodes, we check using DFS if it’s possible to reach one node from the other. 

We create a DFS(x, y, adj, visited), where y is the node from which we are checking if it’s possible to reach x, adj is the adjacency list of the graph we formed, and visited is the set of all the visited nodes.

Algorithm:

• In the function DFS(x, y, adj, visited):
  • If x is in adj[y], return True
  • Iterate child through adj[y]:
    • If child not in visited, insert child is in visited
    • If dfs(x, child, adj, visited) is True, then return True
  • Return False

• Create an empty adjacency list adj.
• Iterate eqn through equations:
  • Set x, op and y as the first character, the next two characters and the last character of eqn, respectively.
  • If op is equal to ‘==’, then,
    • Insert y into adj[x] and x into adj[y]
• Iterate eqn through equations:
  • Set x, op and y as the first character, the next two characters and the last character of eqn, respectively.
  • If op is equal to ‘!=’, then
    • If x is equal to y, return False
    • If dfs(x, y, adj, empty set) is True
      • Return False
• Return True

In this approach, we will make a graph out of equations. We will add an edge between two nodes, and there is  ‘==’ sign between them. This will make all the equal elements in the same graph components and all the unequal in different components.

We will use path compression in the disjoint set to get the component of any node in constant time.

Then we will iterate through every equation and for each equation where there exits ‘!=’ and if they are in the same component, then the equation will not hold, and we will return False. Otherwise, we will return True.

We will create a class Parent(x) that will have two values, parent and rank, where parent is the parent node’s value and rank is the rank of the node used in path compression.

We create a function getParent(x, parents), Where ‘parents’ is a hashmap of every node’s parent and x is the node whose parent we are finding.

We create a function Union(x, y, parents), where ‘parents’ is the array of parents and x and y are nodes we are trying to union.

Algorithm:

• In the function getParent(x, parents)
  • Return x if parents[x].parent  is equal to x otherwise, return getParent(parents[x].parent, parents)
• In the function union(x, y, parents)
  • If parents[x].rank is less than parents[y].rank then
    • Set parents[x].parent as y
  • Otherwise if, parents[y].rank is less than parents[x].rank
    • Set parents[y].parent as x
  • Otherwise, increase parents[x].rank by 1 and set parents[y].parent as x
• In the given function
  • Initialise an empty hashmap parents
  • Iterate eqn through equations
    • Set x, op, and y as the first character, last character of eqn, respectively.
    • Set parents[x] as new instance of Parent(x)
    • Set parents[y] as new instance of Parent(y)
  • Iterate eqn through equations
    • Set x, op, and y as the first character, the next two characters, and the last character of eqn, respectively.
• If op is equal to ‘==’
  • Set xp as getParents(x, parents)
  • Set yp as getParents(y, parents)
  • If xp is not equal to yp then call union(xp, yp, parents)
• Iterate eqn through equations
  • Set x, op and y as the first character, the next two characters and the last character of eqn, respectively.
  • If op is equal to ‘!=’
    • If getParents[x] is equal to getParents[y], then return False
• Return True