Given an array of strings arr[], where each arr[i] is of the form “i==j” or “i!=j”, where i and j are variables representing relationships among them, the task is to check if it is possible to assign values to the variables that satisfy all the relations. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {“i==j”, ” j!=i”}
Output: No
Explanation:
First relation holds true for values i = 1 and j = 1, but the second relation fails for the same set of values. Therefore, print No.Input: arr[] = {“p==q”, “q==r”, “p==r”]
Output: Yes
Explanation:
The assignment of the value 1 in p, q and r satisfies all 3 relations. Therefore, print “Yes”.
Approach: The approach for solving the given problem is to use Union-Find Algorithm. The idea is to traverse the array of strings and go to every equality relation and perform union operation on the two variables. After the traversal, go to every non-equality relation in each string and check if the parent of the two variables is the same or not. Follow the steps below to solve the problem:
- Initialize an array, parent[] of size 26 with 0 and a variable answer as true to store the required result.
- Traverse the array parent[] using the variable i, and set parent[i] as i.
- Now, traverse each string S in the array of strings and if the value of S[i][1] is ‘=’, then perform union operation on S[i][0 – ‘a’] and S[i][3 – ‘a’].
- Again, traverse each the string S in the array of string and do the following:
- If the value of S[i][1] is equal to ‘!’, store the parent of S[i][0 – ‘a’] and S[i][3 – ‘a’] in X and Y respectively.
- If the value of X is equal to Y, set the answer as false.
- After the above steps, if the value of the answer is true then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find parent of each nodeint find(int v, vector<int>& parent){ // If parent[v] is not v, then // recursively call to find the // parent of parent[v] if (parent[v] != v) return parent[v] = find(parent[v], parent); // Otherwise, return v return v;}// Function to perform union of the// two variablesvoid unions(int a, int b, vector<int>& parent){ // Stores the parent of a and b int x = find(a, parent); int y = find(b, parent); // If they are not equal, make // parent[x] = parent[y] if (x != y) parent[x] = parent[y];}// Function to check whether it is// possible to assign values to// variables to satisfy relationsbool equationsPossible( vector<string>& relations){ // Initialize parent array as 0s vector<int> parent(26, 0); // Iterate in range [0, 25] // and make parent[i] = i for (int i = 0; i < 26; i++) { parent[i] = i; } // Store the size of the string int n = relations.size(); // Traverse the string for (auto string : relations) { // Check if it is of the // form "i==j" or not if (string[1] == '=') // Take union of both // the variables unions(string[0] - 'a', string[3] - 'a', parent); } // Traverse the string for (auto string : relations) { // Check if it is of the // form "i!=j" or not if (string[1] == '!') { // Store the parent of // i and j int x = find(string[0] - 'a', parent); int y = find(string[3] - 'a', parent); // If they are equal, // then return false if (x == y) return false; } } return true;}// Driver Codeint main(){ vector<string> relations = { "i==j", "j!=i" }; if (equationsPossible(relations)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ // Function to find parent of each nodestatic int find(int v, ArrayList<Integer> parent){ // If parent[v] is not v, then // recursively call to find the // parent of parent[v] if (parent.get(v) != v) { parent.set(v, find(parent.get(v), parent)); return parent.get(v); } // Otherwise, return v return v;}// Function to perform union of the// two variablesstatic void unions(int a, int b, ArrayList<Integer> parent){ // Stores the parent of a and b int x = find(a, parent); int y = find(b, parent); // If they are not equal, make // parent[x] = parent[y] if (x != y) parent.set(x, parent.get(y));}// Function to check whether it is// possible to assign values to// variables to satisfy relationsstatic boolean equationsPossible(ArrayList<String> relations){ // Initialize parent array as 0s ArrayList<Integer> parent = new ArrayList<Integer>(); for(int i = 0; i < 26; i++) parent.add(0); // Iterate in range [0, 25] // and make parent[i] = i for(int i = 0; i < 26; i++) { parent.set(i, i); } // Store the size of the string int n = relations.size(); // Traverse the string for(String str : relations) { // Check if it is of the // form "i==j" or not if (str.charAt(1) == '=') // Take union of both // the variables unions((int)str.charAt(0) - 97, (int)str.charAt(3) - 97, parent); } // Traverse the string for(String str : relations) { // Check if it is of the // form "i!=j" or not if (str.charAt(1) == '!') { // Store the parent of // i and j int x = find((int)str.charAt(0) - 97, parent); int y = find((int)str.charAt(3) - 97, parent); // If they are equal, // then return false if (x == y) return false; } } return true;}// Driver Codepublic static void main (String[] args){ ArrayList<String> relations = new ArrayList<String>( Arrays.asList("i==j", "j!=i")); if (equationsPossible(relations)) { System.out.println("Yes"); } else { System.out.println("No"); }}}// This code is contributed by rag2127 |
Python3
# Python3 program for the above approach# Function to find parent of each nodedef find(v, parent): # If parent[v] is not v, then # recursively call to find the # parent of parent[v] if (parent[v] != v): parent[v] = find(parent[v], parent) return parent[v] # Otherwise, return v return v# Function to perform union of the# two variablesdef unions(a, b, parent): # Stores the parent of a and b x = find(a, parent) y = find(b, parent) # If they are not equal, make # parent[x] = parent[y] if (x != y): parent[x] = parent[y]# Function to check whether it is# possible to assign values to# variables to satisfy relationsdef equationsPossible(relations): # Initialize parent array as 0s parent = [0]*(26) # Iterate in range [0, 25] # and make parent[i] = i for i in range(26): parent[i] = i # Store the size of the string n = len(relations) # Traverse the string for string in relations: # Check if it is of the # form "i==j" or not if (string[1] == '='): # Take union of both # the variables unions(ord(string[0]) - ord('a'),ord(string[3]) - ord('a'), parent) # Traverse the string for string in relations: # Check if it is of the # form "i!=j" or not if (string[1] == '!'): # Store the parent of # i and j x = find(ord(string[0]) - ord('a'), parent) y = find(ord(string[3]) - ord('a'), parent) # If they are equal, # then return false if (x == y): return False return True# Driver Codeif __name__ == '__main__': relations = ["i==j", "j!=i"] if (equationsPossible(relations)): print("Yes") else: print("No")# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find parent of each node static int find(int v, List<int> parent) { // If parent[v] is not v, then // recursively call to find the // parent of parent[v] if (parent[v] != v) return parent[v] = find(parent[v], parent); // Otherwise, return v return v; } // Function to perform union of the // two variables static void unions(int a, int b, List<int> parent) { // Stores the parent of a and b int x = find(a, parent); int y = find(b, parent); // If they are not equal, make // parent[x] = parent[y] if (x != y) parent[x] = parent[y]; } // Function to check whether it is // possible to assign values to // variables to satisfy relations static bool equationsPossible(List<string> relations) { // Initialize parent array as 0s List<int> parent = new List<int>(); for(int i=0;i<26;i++) parent.Add(0); // Iterate in range [0, 25] // and make parent[i] = i for (int i = 0; i < 26; i++) { parent[i] = i; } // Store the size of the string int n = relations.Count; // Traverse the string foreach( string str in relations) { // Check if it is of the // form "i==j" or not if (str[1] == '=') // Take union of both // the variables unions((int)str[0] - 97, (int)str[3] - 97, parent); } // Traverse the string foreach (string str in relations) { // Check if it is of the // form "i!=j" or not if (str[1] == '!') { // Store the parent of // i and j int x = find((int)str[0] - 97, parent); int y = find((int)str[3] - 97, parent); // If they are equal, // then return false if (x == y) return false; } } return true; } // Driver Code public static void Main() { List<string> relations = new List<string>{ "i==j", "j!=i" }; if (equationsPossible(relations)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } }// This code is contributed by bgangwar59. |
Javascript
<script> // Javascript program for the above approach // Function to find parent of each node function find(v, parent) { // If parent[v] is not v, then // recursively call to find the // parent of parent[v] if (parent[v] != v) return parent[v] = find(parent[v], parent); // Otherwise, return v return v; } // Function to perform union of the // two variables function unions(a, b, parent) { // Stores the parent of a and b let x = find(a, parent); let y = find(b, parent); // If they are not equal, make // parent[x] = parent[y] if (x != y) parent[x] = parent[y]; } // Function to check whether it is // possible to assign values to // variables to satisfy relations function equationsPossible(relations) { // Initialize parent array as 0s let parent = []; for(let i=0;i<26;i++) parent.push(0); // Iterate in range [0, 25] // and make parent[i] = i for (let i = 0; i < 26; i++) { parent[i] = i; } // Store the size of the string let n = relations.length; // Traverse the string for(let str = 0; str < relations.length; str++) { // Check if it is of the // form "i==j" or not if (relations[1] == '=') // Take union of both // the variables unions(relations[0].charCodeAt() - 97, relations[3].charCodeAt() - 97, parent); } // Traverse the string for(let str = 0; str < relations.length; str++) { return false; // Check if it is of the // form "i!=j" or not if (relations[1] == '!') { // Store the parent of // i and j let x = find(relations[0].charCodeAt() - 97, parent); let y = find(relations[3].charCodeAt() - 97, parent); // If they are equal, // then return false if (x == y) return false; } } return true; } let relations = [ "i==j", "j!=i" ]; if (equationsPossible(relations)) { document.write("Yes"); } else { document.write("No"); } // This code is contributed by divyeshrabadiya07.</script> |
Output:
No
Time Complexity: O(N*log M), where M is the number of unique variables in arr[].
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
