等式方程的可满足性

解题思路

通过并查集完成，根据等于号，构建并查集，构建的思路是，可以连通的元素，一定有相同的父亲节点。

通过并查集，判断不等于的元素，只要不在同一个集合中，就满足条件

代码

java

class Solution {
     public boolean equationsPossible(String[] equations) {
    	int [] parents = new int[26];
    	for(int i = 0; i<parents.length;i++) {
    		parents[i] = i;    		    	
    	}
    	for(String eq:equations) {
    		if(eq.charAt(1)=='=') {
    			int index1 = eq.charAt(0)-'a';
    			int index2 = eq.charAt(3)-'a';
    			Union(parents, index1, index2);    		    			
    		}    		    	    		    	    		    	
    	}
    	for(String eq:equations) {
    		if(eq.charAt(1)!='=') {
    			int index1 = eq.charAt(0)-'a';
    			int index2 = eq.charAt(3)-'a';
    			if(find(parents,index1)==find(parents, index2)) {
    				return false;
    			}
    		}    		    	    		    	    		    	
    	}
    	
		return true;
    }
	    	    
	private void Union(int[] parents, int index1, int index2) {
			parents[find(parents, index1)] = find(parents,index2);
	    		    
	    	
	}

	private int find(int[] parents, int index1) {
		int idx = index1;
		while(parents[index1]!=idx) {
			idx = parents[index1];
			index1 = idx;
		}
		return idx;
	}
}