leetcode

0 class Solution {

1 const int SIZE = 26 * 5;

2

3 int hash(const string &st) {

4 static int index = 0;

5 static unordered_map<string, int> um;

6 if (!um.count(st)) um[st] = index++;

7 return um[st];

8 }

9

10 double dfs(vector<vector<pair<int, double>>> &adj, int start, int goal) {

11 stack<pair<int, double>> st;

12 vector<bool> visited(SIZE, false);

13

14 st.push({start, 1});

15 visited[start] = true;

16 while (!st.empty()) {

17 auto [root, value] = st.top();

18 st.pop();

19 if (root == goal) return value;

20 visited[root] = true;

21 for (auto &v : adj[root])

22 if (!visited[v.first]) st.push({v.first, value * v.second});

23 }

24 return -1;

25 }

26

27 public:

28 vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values,

29 vector<vector<string>> &queries) {

30 vector<vector<pair<int, double>>> adj(SIZE, vector<pair<int, double>>());

31 for (int i = 0; i < values.size(); i++) {

32 adj[hash(equations[i][0])].push_back({hash(equations[i][1]), values[i]});

33 adj[hash(equations[i][1])].push_back({hash(equations[i][0]), 1 / values[i]});

34 }

35

36 vector<double> res(queries.size(), -1);

37 for (int i = 0; i < queries.size(); i++) {

38 int start = hash(queries[i][0]), goal = hash(queries[i][1]);

39 if (adj[start].empty() || adj[goal].empty()) continue;

40 res[i] = dfs(adj, start, goal);

41 }

42 return res;

43 }

44 };