-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathequalityEquations.java
More file actions
91 lines (84 loc) · 3.26 KB
/
equalityEquations.java
File metadata and controls
91 lines (84 loc) · 3.26 KB
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.LinkedList;
import java.util.*;
public class equalityEquations {
public static void main(String[] args){
String[] e = {"f==a","a==b","f!=e","a==c","b==e","c==f"};
System.out.println(equationsPossible(e));
}
public static boolean equationsPossible(String[] equations){
int[][] graph = new int[26][26];
for(String part:equations){
int comp1 = part.charAt(0)-'a';
int comp2 = part.charAt(3)-'a';
if(part.charAt(1) == '='){
//graph[comp1][comp2] = 1;
Queue<Integer> queue = new LinkedList<>();
queue.add(comp2);
if(graph[comp1][comp2] == 2 || graph[comp2][comp1] == 2){
return false;
}
graph[comp1][comp2] = 1;
graph[comp2][comp1] = 1;
Set<Integer> visited = new HashSet<>();
visited.add(comp2);
while(!queue.isEmpty()){
int cur = queue.remove();
if(graph[comp1][cur] == 2 || graph[cur][comp1] == 2){
return false;
}
graph[comp1][cur] = 1;
graph[cur][comp1] = 1;
for(int i = 0; i < 26; i++){
if(graph[cur][i] == 1 && !visited.contains(i)){
queue.add(i);
visited.add(i);
}
}
}
}else{
// 不相等的时候
if(comp1 == comp2) return false;
Queue<Integer> queue = new LinkedList<>();
queue.add(comp2);
if(graph[comp1][comp2] == 1 || graph[comp2][comp1] == 1){
return false;
}
graph[comp1][comp2] = 2;
graph[comp2][comp1] = 2;
Set<Integer> visited = new HashSet<>();
while (!queue.isEmpty()){
int cur = queue.remove();
if(graph[comp1][cur] == 1 || graph[cur][comp1] == 1){
return false;
}
graph[comp1][cur] = 2;
graph[cur][comp1] = 2;
for(int i = 0; i < 26; i++){
if(graph[cur][i] == 1 && !visited.contains(i)){
queue.add(i);
visited.add(i);
}
}
}
queue = new LinkedList<>();
queue.add(comp1);
visited = new HashSet<>();
while (!queue.isEmpty()){
int cur = queue.remove();
if(graph[comp2][cur] == 1 || graph[cur][comp2] == 1){
return false;
}
graph[comp2][cur] = 2;
graph[cur][comp2] = 2;
for(int i = 0; i < 26; i++){
if(graph[cur][i] == 1 && !visited.contains(i)){
queue.add(i);
visited.add(i);
}
}
}
}
}
return true;
}
}