public Edge(String val, double weight) {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
double[] res = new double[queries.length];
if (equations.length == 0 || equations[0].length == 0) {
Map<String, List<Edge>> adjList = new HashMap<>();
for (int i = 0; i < equations.length; i++) {
String vertex1 = equations[i][0];
String vertex2 = equations[i][1];
Edge edge1 = new Edge(vertex2, values[i]);
Edge edge2 = new Edge(vertex1, 1 / values[i]);
if (adjList.containsKey(vertex1)) {
adjList.get(vertex1).add(edge1);
List<Edge> edges = new ArrayList<>();
adjList.put(vertex1, edges);
if (adjList.containsKey(vertex2)) {
adjList.get(vertex2).add(edge2);
List<Edge> edges = new ArrayList<>();
adjList.put(vertex2, edges);
for (int i = 0; i < queries.length; i++) {
String start = queries[i][0];
String end = queries[i][1];
Set<String> visited = new HashSet<>();
bfs(start, end, i, visited, adjList, res);
if (res[i] == 0 && !start.equals(end)) {
public void bfs(String start, String end, int index, Set<String> visited, Map<String, List<Edge>> adjList, double[] res) {
if (!adjList.containsKey(start) || !adjList.containsKey(end)) {
Queue<String> queue = new LinkedList<>();
Queue<Double> values = new LinkedList<>();
while (!queue.isEmpty()) {
String curVertex = queue.remove();
double curValue = values.remove();
if (!adjList.containsKey(curVertex)) {
if (curVertex.equals(end)) {
if (visited.contains(curVertex)) {
for (Edge edge : adjList.get(curVertex)) {
String nextVertex = edge.val;
double nextValue = curValue * edge.weight;