C++刷leetcode（990. 等式方程的可满足性）【并查集】

糖逗

题目描述：

1. 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
   
2. 
   
3. 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 
   
4. 
   
5.  
   
6. 
   
7. 示例 1：
   
8. 
   
9. 输入：["a==b","b!=a"]
   
10. 输出：false
    
11. 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
    
12. 示例 2：
    
13. 
    
14. 输出：["b==a","a==b"]
    
15. 输入：true
    
16. 解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
    
17. 示例 3：
    
18. 
    
19. 输入：["a==b","b==c","a==c"]
    
20. 输出：true
    
21. 示例 4：
    
22. 
    
23. 输入：["a==b","b!=c","c==a"]
    
24. 输出：false
    
25. 示例 5：
    
26. 
    
27. 输入：["c==c","b==d","x!=z"]
    
28. 输出：true
    
29.  
    
30. 
    
31. 提示：
    
32. 
    
33. 1 <= equations.length <= 500
    
34. equations[i].length == 4
    
35. equations[i][0] 和&#160;equations[i][3]&#160;是小写字母
    
36. equations[i][1] 要么是&#160;'='，要么是&#160;'!'
    
37. equations[i][2]&#160;是&#160;'='
    
38. 
    
39. 来源：力扣（LeetCode）
    
40. 链接：https://leetcode-cn.com/problems/satisfiability-of-equality-equations
    
41. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     char find_root(char x, map<char, char>&father){
   
4.         if(father[x] != x) return find_root(father[x], father);
   
5.         return x;
   
6.     }
   
7.     void unition(char x, char y, map<char, char>& father, map<char, int>& rank){
   
8.         char temp1 = find_root(x, father);
   
9.         char temp2 = find_root(y, father);
   
10.         if(temp1 != temp2){
    
11.             if(rank[temp1] > rank[temp2]){
    
12.                 father[temp2] = temp1;
    
13.             }else if(rank[temp1] <= rank[temp2]){
    
14.                 if(rank[temp1] == rank[temp2]){
    
15.                     rank[temp1]++;
    
16.                 }
    
17.                 father[temp1] = temp2;
    
18.             }
    
19.         }
    
20.     }
    
21.     bool equationsPossible(vector<string>& equations) {
    
22.         int len = equations.size();
    
23.         set<char> store;
    
24.         for(int i = 0 ; i < len; i++){
    
25.             store.insert(equations[i][0]);
    
26.             store.insert(equations[i][3]);
    
27.         }
    
28.         vector<char>store1(store.begin(), store.end());
    
29.         int len1 = store1.size();
    
30.         map<char, char>father;
    
31.         map<char, int>rank;
    
32.         for(int i = 0; i < len1; i++){
    
33.             father[store1[i]] = store1[i];
    
34.             rank[store1[i]] = 1;
    
35.         }
    
36.         for(int i = 0 ; i < len; i ++){
    
37.             if(equations[i][1] == '='){
    
38.                 unition(equations[i][0], equations[i][3], father, rank);
    
39.             }
    
40.         }
    
41. 
    
42.         for(int i = 0; i < len; i++){
    
43.             if(equations[i][1] == '!'){
    
44.                 char temp1 = find_root(equations[i][0], father);
    
45.                 char temp2 = find_root(equations[i][3], father);
    
46.                 if(temp1 == temp2) return false;
    
47.             }
    
48.         }
    
49.         return true;
    
50. 
    
51.     }
    
52. };

复制代码

糖逗