设有向图G采用邻接表存储,设计算法求G中每个顶点的入度c++
时间: 2024-03-17 11:42:32 浏览: 18
以下是求解G中每个顶点入度的C++代码实现,假设邻接表存储的有向图为G,其中顶点个数为n,邻接表数组为adj[]:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;
struct Edge {
int from, to;
};
vector<Edge> adj[N]; // 邻接表存储
int in_degree[N]; // 存储每个顶点的入度
void calc_in_degree(int n) {
for (int i = 0; i < n; i++) {
for (auto e : adj[i]) {
in_degree[e.to]++;
}
}
}
int main() {
int n, m;
cin >> n >> m;
// 读入有向图
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back({u, v});
}
calc_in_degree(n); // 计算每个顶点的入度
// 输出每个顶点的入度
for (int i = 0; i < n; i++) {
cout << "Vertex " << i << " in_degree: " << in_degree[i] << endl;
}
return 0;
}
```
算法思路:遍历每个顶点的邻接表,对于每条边 $(u, v)$,将顶点 $v$ 的入度加1。最终输出每个顶点的入度即可。