求解无根树中奇数边的数量的c++程序
时间: 2024-02-11 08:05:50 浏览: 18
下面是求解无根树中奇数边的数量的C++程序:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int> G[MAXN];
bool vis[MAXN];
int ans = 0;
void dfs(int u, int p, int dep) {
vis[u] = true;
if (dep & 1) ans++;
for (int v : G[u]) {
if (v == p || vis[v]) continue;
dfs(v, u, dep + 1);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0, 0);
cout << ans << endl;
return 0;
}
```
其中,dfs函数表示从节点u开始深度优先遍历整个树,并统计奇数深度的边的数量。vis[i]表示节点i是否已经被遍历过。在主函数中,我们读入无根树的边,然后从根节点1开始遍历整个树。
相关问题
求解树上所有奇数边的数量程序c++
下面是求解树上所有奇数边的数量的C++程序:
```c++
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
vector<pair<int, int>> G[MAXN]; // 邻接表存储树
bool vis[MAXN];
ll cnt = 0; // 奇数边的数量
void dfs(int u, ll d) { // d表示到达当前节点u时所经过的边的权值之和
vis[u] = true;
if (d % 2 == 1) cnt++; // 如果d是奇数,则cnt加1
for (auto [v, w] : G[u]) {
if (vis[v]) continue;
dfs(v, d + w); // 递归搜索相邻节点v
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
dfs(1, 0);
cout << cnt << endl;
return 0;
}
```
其中,dfs函数表示从节点u开始深度优先遍历整个树,并统计奇数深度的边的数量。vis[i]表示节点i是否已经被遍历过。在主函数中,我们读入无根树的边,然后从根节点1开始遍历整个树。最终,我们输出奇数边的数量cnt。
蒙特卡洛法串行求解Pi值C++程序
以下是串行求解 Pi 值的 C++ 代码,使用蒙特卡洛方法:
```C++
#include <iostream>
#include <random>
int main() {
const int num_points = 1000000; // 模拟点数
int num_in_circle = 0; // 圆内点数
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> dis(-1.0, 1.0);
for (int i = 0; i < num_points; ++i) {
double x = dis(gen);
double y = dis(gen);
if (x * x + y * y <= 1) {
++num_in_circle;
}
}
double pi = 4.0 * num_in_circle / num_points;
std::cout << "Pi = " << pi << std::endl;
return 0;
}
```
该程序使用 `std::random_device` 和 `std::mt19937` 生成器生成均匀分布在 $[-1,1]$ 区间内的随机数,模拟在单位正方形内随机投点,判断每个点是否在以原点为圆心、半径为 $1$ 的圆内,最后根据圆内点数和总点数的比例计算 Pi 值。