C++でのT秒後のカエルの位置

n個の頂点で構成される無向ツリーが1つあるとします。頂点には1からnまでの番号が付けられています。これで、カエルは頂点1からジャンプを開始します。カエルは、現在の頂点から、訪問していない別の頂点に隣接している場合、1秒でジャンプできます。カエルは、訪れた頂点に戻ることはできません。カエルが複数の頂点にジャンプできる場合は、そのうちの1つにランダムにジャンプします

確率が同じ場合、それ以外の場合、カエルが訪問していない頂点にジャンプできない場合、同じ頂点で永久にジャンプします。

ツリーはエッジの配列として与えられます。 t秒後にカエルが頂点ターゲットにいる確率を見つける必要があります。

したがって、入力がnが7、tが2、ターゲットが4の場合、ツリーは-

その場合、グラフからのように、出力は0.1666になります。カエルは頂点1から始まり、2秒後に頂点2に0.3333の確率でジャンプし、2秒後に頂点4に0.5の確率でジャンプします。したがって、2秒後にカエルが頂点4にいる確率は0.3333 * 0.5 =1.6665。

これを解決するには、次の手順に従います-

• ret：=1

• 訪問した1セットを定義する

• 関数dfs（）を定義します。これにより、ノード、開始、エッジのリストg、時間、t、1つのスタックst、

  が取得されます。

• ノードがvisitedのメンバーである場合、-

  • falseを返す

• 訪問先にノードを挿入

• ノードが1と同じ場合、-

  • tt：=時間、ok：=true

  • trueを返す

• 初期化i：=0の場合、i

  • g [node、i]をst

    に挿入します

  • dfs（g [node、i]、start、g、time + 1、t、st）が真の場合、-

    • trueを返す

  • stから要素を削除

• falseを返す

• メインの方法から、次のようにします-

• ret：=1

• ok：=false

• サイズn+1のリストグラフの配列を定義します

• サイズn+1

  のリストgraph2の配列を定義します

• 初期化i：=0の場合、i <エッジのサイズの場合、更新（iを1増やします）、実行-

  • グラフの最後にedges[i、1]を挿入します[edges [i、0]]

  • グラフの最後にedges[i、0]を挿入します[edges [i、1]]

• 1つのスタックstを定義する

• dfs（target、target、graph、0、t、st）

• （stが空ではない）間、-

  • node：=stの最上位要素

  • sz：=グラフのサイズ[ノード]

  • ノードが1に等しくない場合、-

    • （szを1減らします）

  • ret：=ret *（1.0 / sz）

  • stから要素を削除

• tt> tの場合、-

  • 0を返す

• ttがtと同じ場合、-

  • retを返す

• tt =1の場合、-

  • 0を返す

• return（tt1の場合は0、それ以外の場合はret）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   double ret = 1;
   bool ok;
   set<int> visited;
   int tt;
   bool dfs(int node, int start, vector<int> g[], int time, int t,
   stack<int>& st){
      if (visited.count(node))
      return false;
      visited.insert(node);
      if (node == 1) {
         tt = time;
         ok = true;
         return true;
      }
      for (int i = 0; i < g[node].size(); i++) {
         st.push(g[node][i]);
         if (dfs(g[node][i], start, g, time + 1, t, st))
         return true;
         ;
         st.pop();
      }
      return false;
   }
   double frogPosition(int n, vector<vector<int> >& edges, int t,
   int target){
      ret = 1;
      ok = false;
      vector<int> graph[n + 1];
      vector<int> graph2[n + 1];
      for (int i = 0; i < edges.size(); i++) {
         graph[edges[i][0]].push_back(edges[i][1]);
         graph[edges[i][1]].push_back(edges[i][0]);
      }
      stack<int> st;
      dfs(target, target, graph, 0, t, st);
      while (!st.empty()) {
         int node = st.top();
         double sz = (double)graph[node].size();
         if (node != 1)
         sz--;
         ret *= (1.0 / sz);
         st.pop();
      }
      if (tt > t)
      return 0;
      if (tt == t)
      return ret;
      if (tt < t && target == 1 && graph[target].size() >= 1)
      return 0;
      return tt < t && graph[target].size() > 1 ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
   cout << (ob.frogPosition(7,v,2,4));
}

入力

7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4

出力

0.166667