n개의 꼭짓점으로 구성된 하나의 무방향 트리가 있다고 가정합니다. 정점은 1에서 n까지 번호가 지정됩니다. 이제 개구리는 정점 1에서 점프하기 시작합니다. 개구리는 현재 정점에서 방문하지 않은 다른 정점이 인접해 있으면 1초 안에 다른 정점으로 점프할 수 있습니다. 개구리는 방문한 정점으로 돌아갈 수 없습니다. 개구리가 여러 정점으로 이동할 수 있는 경우 무작위로 그 중 하나로 이동합니다.
확률이 같으면 개구리가 방문하지 않은 정점으로 점프할 수 없을 때 같은 정점에서 영원히 점프합니다.
트리는 에지의 배열로 제공됩니다. t초 후에 개구리가 정점 목표물에 있을 확률을 찾아야 합니다.
따라서 입력이 n은 7, t는 2, 대상은 4, 트리는 -
와 같습니다. 
그래프에서와 같이 출력은 0.1666이 됩니다. 개구리는 정점 1에서 시작하여 두 번째 1 후에 정점 2로 0.3333 확률로 점프한 다음 두 번째 2 후에 정점 4로 0.5 확률로 점프합니다. 따라서 개구리가 2초 후에 정점 4에 있을 확률은 0.3333 * 0.5 =1.6665.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
렛 :=1
-
방문한 한 세트 정의
-
dfs() 함수를 정의하면 노드, 시작, 가장자리 목록 g, 시간, t, 스택 st,
가 필요합니다. -
노드가 방문의 구성원이면 -
-
거짓을 반환
-
-
방문한 노드에 삽입
-
노드가 1과 같으면 -
-
tt :=시간, 확인 :=사실
-
true를 반환
-
-
for initialize i :=0, i
-
g[노드, i]를 st
에 삽입 -
dfs(g[node, i], start, g, time + 1, t, st)가 참이면 -
-
true를 반환
-
-
st
에서 요소 삭제
-
-
거짓을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
렛 :=1
-
확인 :=거짓
-
크기가 n + 1인 목록 그래프의 배열을 정의합니다.
-
크기가 n + 1인 목록 graph2의 배열을 정의하십시오.
-
initialize i :=0의 경우, i <모서리의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
-
그래프의 끝에 edge[i, 1] 삽입[edges[i, 0]]
-
그래프의 끝에 edge[i, 0] 삽입[edges[i, 1]]
-
-
하나의 스택 정의
-
dfs(대상, 대상, 그래프, 0, t, st)
-
동안(st가 비어 있지 않음) -
-
node :=st의 최상위 요소
-
sz :=그래프[노드]의 크기
-
노드가 1이 아닌 경우 -
-
(sz를 1 감소)
-
-
렛 :=렛 * (1.0 / sz)
-
st
에서 요소 삭제
-
-
tt> t이면 -
-
0 반환
-
-
tt가 t와 같으면 -
-
리턴 렛
-
-
tt
=1이면 - -
0 반환
-
-
반환(tt
1이면 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