class Solution {
public boolean equationsPossible(String[] equations) {
UnionFind unionfind=new UnionFind(26);
for(String s:equations){
if(s.charAt(1)=='=')
{
int index1=s.charAt(0)-'a';
int index2=s.charAt(3)-'a';
unionfind.union(index1,index2);
}
}
for(String s:equations){
if(s.charAt(1)=='!')
{
int index1=s.charAt(0)-'a';
int index2=s.charAt(3)-'a';
if(unionfind.find(index1)==unionfind.find(index2)){
return false;
}
}
}
return true;
}
private class UnionFind{
private int[] parent;
public UnionFind(int n)
{
this.parent=new int[n];
for(int i=0;i<n;i++)
{
parent[i]=i;
}
}
public void union(int l1,int l2){
if(find(l1)==find(l2)) return;
parent[find(l1)]=find(l2);
}
public int find(int x)
{
if(parent[x]!=x)
{
parent[x]=find(parent[x]);
}
return parent[x];
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48