{"id":4824,"date":"2019-02-10T02:21:32","date_gmt":"2019-02-10T10:21:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4824"},"modified":"2020-01-29T20:22:17","modified_gmt":"2020-01-30T04:22:17","slug":"leetcode-990-satisfiability-of-equality-equations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-990-satisfiability-of-equality-equations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 990. Satisfiability of Equality Equations"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode Weekly Contest 123 (989, 990, 991, 992) - \u5237\u9898\u627e\u5de5\u4f5c\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/FZPtxuxArLU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given an array&nbsp;equations&nbsp;of strings that represent relationships between variables, each string&nbsp;<code>equations[i]<\/code>&nbsp;has length&nbsp;<code>4<\/code>&nbsp;and takes one of two different forms:&nbsp;<code>\"a==b\"<\/code>&nbsp;or&nbsp;<code>\"a!=b\"<\/code>.&nbsp; Here,&nbsp;<code>a<\/code>&nbsp;and&nbsp;<code>b<\/code>&nbsp;are lowercase letters (not necessarily different) that represent one-letter variable names.<\/p>\n\n\n\n<p>Return&nbsp;<code>true<\/code>&nbsp;if and only if it is possible to assign integers to variable names&nbsp;so as to satisfy all the given equations.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[\"a==b\",\"b!=a\"]\n<strong>Output: <\/strong>false\n<strong>Explanation: <\/strong>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.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[\"b==a\",\"a==b\"]\n<strong>Output: <\/strong>true\n<strong>Explanation: <\/strong>We could assign a = 1 and b = 1 to satisfy both equations.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[\"a==b\",\"b==c\",\"a==c\"]\n<strong>Output: <\/strong>true\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[\"a==b\",\"b!=c\",\"c==a\"]\n<strong>Output: <\/strong>false\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[\"c==c\",\"b==d\",\"x!=z\"]\n<strong>Output: <\/strong>true\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><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;and&nbsp;<code>equations[i][3]<\/code>&nbsp;are lowercase letters<\/li><li><code>equations[i][1]<\/code>&nbsp;is either&nbsp;<code>'='<\/code>&nbsp;or&nbsp;<code>'!'<\/code><\/li><li><code>equations[i][2]<\/code>&nbsp;is&nbsp;<code>'='<\/code><\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Union Find<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 12 ms, 7.1 MB\nclass Solution {\npublic:\n  bool equationsPossible(vector<string>& equations) {        \n    iota(begin(parents_), end(parents_), 0);    \n    for (const auto& eq : equations)     \n      if (eq[1] == '=')\n        parents_[find(eq[0])] = find(eq[3]);\n    for (const auto& eq : equations)     \n      if (eq[1] == '!' && find(eq[0]) == find(eq[3]))        \n          return false;\n    return true;\n  }\nprivate:\n  array<int, 128> parents_;\n  int find(int x) {\n    if (x != parents_[x])\n      parents_[x] = find(parents_[x]);\n    return parents_[x];\n  }  \n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array&nbsp;equations&nbsp;of strings that represent relationships between variables, each string&nbsp;equations[i]&nbsp;has length&nbsp;4&nbsp;and takes one of two different forms:&nbsp;&#8220;a==b&#8221;&nbsp;or&nbsp;&#8220;a!=b&#8221;.&nbsp; Here,&nbsp;a&nbsp;and&nbsp;b&nbsp;are lowercase letters (not necessarily different) that&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[465,77,177,113],"class_list":["post-4824","post","type-post","status-publish","format-standard","hentry","category-graph","tag-equation","tag-graph","tag-medium","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4824","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4824"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4824\/revisions"}],"predecessor-version":[{"id":6181,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4824\/revisions\/6181"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4824"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4824"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4824"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}