satisfiability-of-equality-equations

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of strings <code>equations</code> that represent relationships between variables where each string <code>equations[i]</code> is of length <code>4</code> and takes one of two different forms: <code>&quot;xi==yi&quot;</code> or <code>&quot;xi!=yi&quot;</code>.Here, <code>xi</code> and <code>yi</code> are lowercase letters (not necessarily different) that represent one-letter variable names.

Return <code>true</code> if it is possible to assign integers to variable names so as to satisfy all the given equations, or <code>false</code> otherwise.

&nbsp;
Example 1:

<pre>
Input: equations = [&quot;a==b&quot;,&quot;b!=a&quot;]
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.
</pre>

Example 2:

<pre>
Input: equations = [&quot;b==a&quot;,&quot;a==b&quot;]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= equations.length &lt;= 500</code></li>
	<li><code>equations[i].length == 4</code></li>
	<li><code>equations[i][0]</code> is a lowercase letter.</li>
	<li><code>equations[i][1]</code> is either <code>&#39;=&#39;</code> or <code>&#39;!&#39;</code>.</li>
	<li><code>equations[i][2]</code> is <code>&#39;=&#39;</code>.</li>
	<li><code>equations[i][3]</code> is a lowercase letter.</li>
</ul>

equationsPossible

Satisfiability of Equality Equations

Union Find

Graph

Array

String

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 <code>equations[i]</code> 的长度为 <code>4</code>，并采用两种不同的形式之一：<code>&quot;a==b&quot;</code> 或&nbsp;<code>&quot;a!=b&quot;</code>。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回&nbsp;<code>true</code>，否则返回 <code>false</code>。&nbsp;

&nbsp;

<ol>
</ol>

示例 1：

<pre>输入：[&quot;a==b&quot;,&quot;b!=a&quot;]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
</pre>

示例 2：

<pre>输入：[&quot;b==a&quot;,&quot;a==b&quot;]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
</pre>

示例 3：

<pre>输入：[&quot;a==b&quot;,&quot;b==c&quot;,&quot;a==c&quot;]
输出：true
</pre>

示例 4：

<pre>输入：[&quot;a==b&quot;,&quot;b!=c&quot;,&quot;c==a&quot;]
输出：false
</pre>

示例 5：

<pre>输入：[&quot;c==c&quot;,&quot;b==d&quot;,&quot;x!=z&quot;]
输出：true
</pre>

&nbsp;

提示：

<ol>
	<li><code>1 &lt;= equations.length &lt;= 500</code></li>
	<li><code>equations[i].length == 4</code></li>
	<li><code>equations[i][0]</code> 和&nbsp;<code>equations[i][3]</code>&nbsp;是小写字母</li>
	<li><code>equations[i][1]</code> 要么是&nbsp;<code>&#39;=&#39;</code>，要么是&nbsp;<code>&#39;!&#39;</code></li>
	<li><code>equations[i][2]</code>&nbsp;是&nbsp;<code>&#39;=&#39;</code></li>
</ol>