刷题笔记27——并查集

很长一段时间，我的生活看似马上就要开始了。但是总有一些障碍阻挡着，有些事得先解决，有些工作还有待完成，时间貌似不够用，还有一笔债务8要去付清，然后生活就会开始。最后我终于明白，这些障碍，正是我的生活。 ——艾弗里德·德索萨

990. 等式方程的可满足性（一个比较经典的并查集例子）

class Solution {public boolean equationsPossible(String[] equations) {UF uf = new UF(26);for(String eq:equations){if(eq.charAt(1) == '='){char x = eq.charAt(0);char y = eq.charAt(3);uf.union(x-'a',y-'a');}}for(String eq:equations){if(eq.charAt(1) == '!'){char x = eq.charAt(0);char y = eq.charAt(3);if(uf.connocted(x-'a',y-'a')){return false;}}}return true;}  
}class UF{private int count;private int[] parent;public UF(int n){this.count = n;parent = new int[n];for(int i=0;i<n;i++){parent[i] = i;}}public void union(int p,int q){int rootP = find(p);int rootQ = find(q);if(rootP == rootQ) return;parent[rootP] = rootQ;count--;}public boolean connocted(int p,int q){int rootP = find(p);int rootQ = find(q);return rootP==rootQ;}public int find(int p){if(p!= parent[p]){parent[p] = find(parent[p]);}return parent[p];}public int count(){return count;}}

后续再补充真题