Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

👨‍💻 Алгоритм:

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

3⃣Обработка запросов:
Пройдитесь по всем запросам и используйте граф для вычисления результатов каждого запроса.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        var graph = new Dictionary<string, Dictionary<string, double>>();

        for (int i = 0; i < equations.Count; i++) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            if (!graph.ContainsKey(A)) graph[A] = new Dictionary<string, double>();
            if (!graph.ContainsKey(B)) graph[B] = new Dictionary<string, double>();
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }

        double Bfs(string start, string end) {
            if (!graph.ContainsKey(start) || !graph.ContainsKey(end)) return -1.0;
            var q = new Queue<(string, double)>();
            q.Enqueue((start, 1.0));
            var visited = new HashSet<string>();
            
            while (q.Count > 0) {
                var (current, curProduct) = q.Dequeue();
                if (current == end) return curProduct;
                visited.Add(current);
                foreach (var neighbor in graph[current]) {
                    if (!visited.Contains(neighbor.Key)) {
                        q.Enqueue((neighbor.Key, curProduct * neighbor.Value));
                    }
                }
            }
            return -1.0;
        }

        var results = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            string C = queries[i][0], D = queries[i][1];
            results[i] = Bfs(C, D);
        }
        return results;
    }
}

Ставь 👍 и забирай 📚 Базу знаний