输出整个C++代码:统计0入度到0出度点的路径数量的算法
时间: 2024-03-25 22:35:36 浏览: 11
以下是一个简单的C++代码实现,用于统计0入度到0出度点的路径数量:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int count_paths(vector<vector<int>> adj_list) {
// 统计每个节点的入度和出度
vector<int> indegrees(adj_list.size(), 0);
vector<int> outdegrees(adj_list.size(), 0);
for (int u = 0; u < adj_list.size(); u++) {
for (int v : adj_list[u]) {
indegrees[v]++;
outdegrees[u]++;
}
}
// 找到入度为0的节点作为起点
int start_node = distance(indegrees.begin(), find(indegrees.begin(), indegrees.end(), 0));
// 定义一个数组dp[i],表示从起点到节点i的路径数量
vector<int> dp(adj_list.size(), 0);
dp[start_node] = 1;
// 对于每个节点i,遍历它的出边j,更新dp[j] = dp[j] + dp[i]
for (int u = 0; u < adj_list.size(); u++) {
for (int v : adj_list[u]) {
dp[v] += dp[u];
}
}
// 最终统计出度为0的节点的dp值之和就是0入度到0出度点的路径数量
int total_paths = 0;
for (int u = 0; u < adj_list.size(); u++) {
if (outdegrees[u] == 0) {
total_paths += dp[u];
}
}
return total_paths;
}
int main() {
// 构建有向图邻接表
vector<vector<int>> adj_list = {
{1, 2},
{3, 4},
{4},
{4},
{},
};
// 统计0入度到0出度点的路径数量
int num_paths = count_paths(adj_list);
cout << "Number of paths from 0-indegree to 0-outdegree nodes: " << num_paths << endl;
return 0;
}
```
其中,adj_list是邻接表表示的有向图,每个元素adj_list[u]是一个vector,表示节点u的出边所连接的节点。例如,adj_list[0] = {1, 2}表示节点0有两条出边分别连接节点1和2。