Compruebe si es posible asignar valores tales que se satisfagan todas las relaciones dadas

Dada una array de strings arr[] , donde cada arr[i] tiene la forma “i==j” o “i!=j” , donde i y j son variables que representan las relaciones entre ellas, la tarea es comprobar si es posible asignar valores a las variables que satisfacen todas las relaciones. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr[] = {“i==j”, ” j!=i”}
Salida: No
Explicación:
La primera relación se cumple para los valores i = 1 y j = 1, pero la segunda relación falla para el mismo conjunto de valores. Por lo tanto, imprima No.

Entrada: arr[] = {“p==q”, “q==r”, “p==r”]
Salida: Sí
Explicación:
La asignación del valor 1 en p, q y r satisface las 3 relaciones. Por lo tanto, imprima «Sí».

Enfoque: el enfoque para resolver el problema dado es usar el algoritmo Union-Find . La idea es atravesar la array de strings e ir a cada relación de igualdad y realizar la operación de unión en las dos variables. Después del recorrido, vaya a cada relación de no igualdad en cada string y verifique si el padre de las dos variables es el mismo o no. Siga los pasos a continuación para resolver el problema:

1. Inicialice una array , parent[] de tamaño 26 con 0 y una respuesta variable como verdadera para almacenar el resultado requerido.
2. Recorra la array parent[] usando la variable i y establezca parent[i] como i .
3. Ahora, recorra cada string S en la array de strings y si el valor de S[i][1] es ‘=’ , realice la operación de unión en S[i][0 – ‘a’] y S[i][ 3 – ‘a’] .
4. Nuevamente, recorra cada string S en la array de strings y haga lo siguiente:
   1. Si el valor de S[i][1] es igual a ‘!’ , almacene el padre de S[i][0 – ‘a’] y S[i][3 – ‘a’] en X e Y respectivamente.
   2. Si el valor de X es igual a Y , establezca la respuesta como falsa .
5. Después de los pasos anteriores, si el valor de la respuesta es verdadero , imprima «Sí» , de lo contrario, imprima «No» .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find parent of each node
int 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 variables
void 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 relations
bool 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 Code
int main()
{
    vector<string> relations
        = { "i==j", "j!=i" };
 
    if (equationsPossible(relations)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to find parent of each node
static 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 variables
static 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 relations
static 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 Code
public 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 program for the above approach
 
# Function to find parent of each node
def 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 variables
def 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 relations
def 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 Code
if __name__ == '__main__':
    relations = ["i==j", "j!=i"]
    if (equationsPossible(relations)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using 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.

<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>

No

Complejidad temporal: O(N*log M), donde M es el número de variables únicas en arr[]. 
Espacio Auxiliar: O(1)