Advertisement
Guest User

graph division problem dfs

a guest
Nov 21st, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.19 KB | None | 0 0
  1. class Solution {
  2. public:
  3.  
  4. double dfs (unordered_map < string , vector < pair <string , double> > > &graph, string cur, string dist, double &ans, unordered_map <string, bool> &vis)
  5. {
  6. if (cur == dist)
  7. {
  8. return true;
  9. }
  10. vis[cur] = true;
  11.  
  12. vector <pair <string , double> > vec = graph[cur];
  13.  
  14. for (int i = 0 ; i < vec.size(); i++ )
  15. {
  16. string eq = vec[i].first;
  17. double w = vec[i].second;
  18.  
  19. if (vis[eq] == false)
  20. {
  21. vis[eq] = true;
  22. ans *= w;
  23. if ( dfs (graph, eq, dist, ans, vis))
  24. {
  25. return true;
  26. }
  27. ans /= w;
  28. vis[eq] = false;
  29. }
  30. }
  31. return false;
  32. }
  33. vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
  34.  
  35. unordered_map < string , vector < pair <string , double> > > graph;
  36. vector <double> res;
  37. int sz = equations.size();
  38.  
  39. for (int i = 0 ; i < sz ; i++ )
  40. {
  41.  
  42. string a = equations[i][0];
  43. string b = equations[i][1];
  44.  
  45. double ans = values[i];
  46.  
  47. graph[a].push_back ({b,ans});
  48. graph[b].push_back ({a,(1/ans)});
  49. }
  50.  
  51. sz = queries.size();
  52.  
  53. for (int i = 0 ; i <sz; i++ )
  54. {
  55.  
  56. string a = queries[i][0];
  57. string b = queries[i][1];
  58.  
  59. unordered_map <string, bool> vis;
  60.  
  61. double ans = -1;
  62. if (graph.find(a) == graph.end() || graph.find(b) == graph.end())
  63. {
  64. res.push_back (ans);
  65. continue;
  66. }
  67.  
  68. double dfs_ans = 1;
  69. bool path = dfs (graph, a, b,dfs_ans,vis);
  70.  
  71. if (path)
  72. res.push_back (dfs_ans);
  73. else
  74. res.push_back (ans);
  75.  
  76. }
  77. return res;
  78. }
  79. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement