簡介：中，題意為評估所有等式是否自相合理。最直覺的方式是依序檢查每個等式是否合理於前面所有成立的等式們，但這方法十分複雜。因此我們可以先維護所有的等式，再去檢驗所有的不等式是否合理？實作的部分提供兩種資料結構，一種是陣列與集合的混合體，另一種是純陣列，即為併查集 (union find)。
一、我的想法
（一）概念
 |
| 我的方法的概念 |
題意為給予數個等式與不等式，並回傳這些等式與不等式是否自相合理？如果自相合理，則回傳1 (true)；如果自相矛盾，則回傳0 (false)。等式左右兩邊為26個小寫字母 (a-z)，不會有其他可能的符號出現。
如上圖的輸入為{"a==b","b!=c","c==a"}，有兩個等式與一個不等式。有一個最直覺的方式即是，依序檢查每個等式是否矛盾於前面所有成立的等式們。假設等式1 ("a==b")成立，則檢查等式2 ("b!=c")是否矛盾等式1，如果等式2沒有和等式1矛盾，則等式2成立。之後再檢查等式3 ("c==a")，是否矛盾於等式1&2，顯然等式3與等式1&2矛盾，因此回傳0 (false)。
但這方法十分複雜，因為要同時維護成立的等式以及成立的不等式，而且維護不等式是比較麻煩的。因此我們先只維護所有的等式成一個等式表 (isEqu table)，相等於假設所有的等式都成立。這個假設是合理的，因為所有等式都成立，必不會自相矛盾。第一步建立好等式表後，第二步再拿等式表，依序檢查每一個不等式。
（二）實作
 |
| 我的方法的第一步：建構等式表 |
第一步先建立等式表 (isEqu)，這個等式表是由陣列 (vector)和集合 (unordered_set)所組成的資料結構。每個集合代表一組相等的關係，為了快速知道這個字母是否已經存在於等式表中，額外維護了字母存在表 (letters)；以及快速找到不等式，也維護不等式表 (notEqu)，不等式表只紀錄不等式於equations的位置。
等式左邊的變數為lett1，等式右邊的變數為lett2，而建構等式表時，會有4種情境，分別為：
- lett1不存在且lett2不存在：將lett1和lett2一起放入新的集合中
- lett1存在且lett2不存在：將lett2放入lett1所屬的集合中
- lett1不存在且lett2存在：將lett1放入lett2所屬的集合中
- lett1存在且lett2存在：如果lett1和lett2兩屬於不同集合，則將lett1和lett2所在的集合合併
 |
| findIsEqu()：尋找lett在等式表中的位置 |
findIsEqu()功能為尋在lett在等式表的位置，並將位置紀錄在j之中。
 |
| 我的方法的第二步：檢查所有的不等式 |
第二步即為利用等式表，依序檢查所有的不等式。再檢查不等式前，必須確保不等式左右兩邊的變數皆為不同，如果變數皆為相同，則為自相矛盾，回傳0 (false)。在建構等式表時，會有4種狀況，但再檢查不等式時，我們只要檢查1種狀況即可，即為lett1和lett2同時存在於等式表時。
因為我們不在意不存在於等式表中的字母，因此還有一個隱藏的假設即為，不在等式表的字母，可以等於或不等於任何字母，即這些字母是不受到等式表的規範。因此不等式中，只要一個字母不存在於等式表中，此不等式必定成立。在lett1和lett2同時存在於等式表時，如果lett1和lett2屬於相同的集合時，則不等式不成立。
二、併查集 (union find)
（一）概念
 |
| Union find method |
在我的想法中，有兩個很重要的觀察分別為：
- 所有等式都成立，必不會自相矛盾 -> 等式表
- 只要一個字母不存在於等式表中，此不等式必定成立 -> 不存在於等式表的字母，不受等式規範
我的等式表中，只運用了觀察1，是否能再加入觀察2的限制？觀察2另一個意涵為不存在於等式表的字母，不受等式規範。換句話說，不在等式表中的字母，必定可以是不等式。因此引來第二重要的假設，即為所有字母都是不相等的。
綜合以上論述，我們的第1假設為所有字母皆不相等，第2假設為所有等式皆成立，第2假設會去修改第1假設的規定，以至於讓部分字母為不相等。由於引進第1假設，因此我們的資料結構就可以捨棄集合結構，而變成單純的陣列結構，但集合概念仍依然存在，這樣的資料結構為併查集 (union find)。
因此一開始初始化讓所有字母都不一樣，再透過等式的加入，去更新併查集。最後利用完成的併查集，依序檢查每個不等式是否成立？
（二）實作
 |
| Union find method code |
併查集中一開始每個人都是集團的老闆 (line 90. uf[i] == i)，集團之間會透過合併(line 92-93)，而增加集團內的人數。併查集內儲存所屬集合的上司，如果自己就是自己的上司，則代表自己是此集團的老闆，而每個集團只會有一個老闆。
find(x)功能為找到x所屬集團的老闆，如果x != uf[x]，則繼續尋找x上司 (uf[x])的上司，直到找到老闆 （自己為自己的上司），尋找的過程中並順便更新uf[x]值 (line 85)，使得uf[x]直接存儲老闆，避免出現過多的上司。選擇上司的原則為右邊變數為左邊變數的上司，因此右邊集團會併吞左邊集團(line 93)。
舉例子1：{"a==b, c==a"}，一開始初始化uf[a] = 1、uf[b] = 2、uf[c] = 3，接下進行併吞，"a==b"代表b集團併吞a集團，因此uf[a] = 2、uf[b] = 2、uf[c] = 3，"c==a"代表a集團併吞c集團，而a集團的老闆為b，故uf[a] = 2、uf[b] = 2、uf[c] = 2。最後line 94-96 利用uf檢查所有的不等式。
再舉例子2：{"a==b","c==a", "d==e", "f==d", "a==d", "g==a"}，一開始初始化uf[a] = 1、uf[b] = 2、uf[c] = 3、uf[d] = 4、uf[e] = 5、uf[f] = 6、uf[g] = 7。
- "a==b"代表b併吞a：uf[a] = 2、uf[b] = 2、uf[c] = 3、uf[d] = 4、uf[e] = 5、uf[f] = 6、uf[g] = 7
- "c==a"代表a併吞c：uf[a] = 2、uf[b] = 2、uf[c] = 2、uf[d] = 4、uf[e] = 5、uf[f] = 6、uf[g] = 7
- "d==e"代表e併吞d：uf[a] = 2、uf[b] = 2、uf[c] = 2、uf[d] = 5、uf[e] = 5、uf[f] = 6、uf[g] = 7
- "f==d"代表d併吞f：uf[a] = 2、uf[b] = 2、uf[c] = 2、uf[d] = 5、uf[e] = 5、uf[f] = 5、uf[g] = 7
- "a==d"代表d併吞a：uf[a] = 2、uf[b] =5 、uf[c] = 2、uf[d] = 5、uf[e] = 5、uf[f] = 5、uf[g] = 7
- "g==a"代表a併吞g : uf[a] = 5、uf[b] =5 、uf[c] = 2、uf[d] = 5、uf[e] = 5、uf[f] = 5、uf[g] = 5
從例子2中可以得知，d (e集團)併吞a (b集團)時，一開始不是直接併吞下屬a，而是直接併吞老闆b，當下一次e集團併吞其他集團時，可能會順便更新e集團的值。所以在a (e集團) 併吞g (g集團)時 時，會直接併吞老闆g，以及更新e集團的uf[a]值。uf[c]之所以還沒被更新，是因為在尋找a的老闆時，不會找到c，因此uf[c]尚未被更新。
三、相關文章
請詳見LeetCode相關文章
留言
張貼留言