北郵oj-尋找寶藏

題目要求

給定節點，要求找到從根節點往該節點尋找的機率。

AC代碼

#include <bits/stdc++.h>
#include <vector>

using namespace std;

struct TreeNode {		//每個節點儲存一個兒子數組和父親
	int father;
	vector<int> son;
	TreeNode(): father(-1), son() {
		son.clear();
	}
};

int main() {
	int N, M, L;
	TreeNode T[1001];
	scanf("%d%d%d", &N, &M, &L);
	int a, b;
	while (M--) {
		scanf("%d%d", &a, &b);
		T[a].son.push_back(b);
		T[b].father = a;
	}
	L = T[L].father;
	int sum = 1;
	do {							//從給定節點出發，找到根節點結束
		sum *= T[L].son.size();
		L = T[L].father;
	} while (L != -1);
	double output = (double)1.0 / sum;
	printf("%.6lf\n", output);
	return 0;
}