用python编码,请输出有向连通图顶点v的入度。 输入格式: 有多组测试数据,每组数据请依次输入图中各顶点的值,每个顶点值以回车间隔,并以#作为输入结束符;再请依次输入图中每条弧的两个顶点值,两个顶点值以空格作为间隔,每输入一组后进行换行,仍以#结束输入;最后一行为某顶点v。 输出格式: 每组输出占一行,为顶点v的入度。 输入样例: 在这里给出一组输入。例如: A B C D E F # A B A F B C B D C E D E # E 输出样例: 在这里给出相应的输出。例如: 2
时间: 2024-03-13 19:42:41 浏览: 16
根据题目要求,我们需要读取多组输入数据,对于每组数据,先读取所有顶点的值,然后根据输入的弧的信息构建有向图。最后读取目标顶点的值,输出其入度即可。
以下是示例代码:
```python
while True:
vertex_list = input().split()
if vertex_list == ['#']:
break
graph = {v: [] for v in vertex_list}
while True:
arc = input().split()
if arc == ['#']:
break
graph[arc[1]].append(arc[0])
v = input().strip()
print(len([node for node in graph if v in graph[node]]))
```
首先,我们进入一个无限循环,每次读取一组输入数据。在每组数据中,我们先读取所有顶点的值,用它们构建一个空的有向图。然后,我们一直读取输入,直到遇到`#`为止,每次读取两个顶点值,将第二个顶点作为起点,第一个顶点作为终点,将这条弧加入到有向图中。
最后,我们读取目标顶点的值,并遍历有向图中的所有节点,对于每个节点,如果目标顶点在该节点的出边列表中,就将入度计数器加1。最终,输出入度计数器即可。
相关问题
请输出有向连通图顶点v的入度。 输入格式: 有多组测试数据,每组数据请依次输入图中各顶点的值,每个顶点值以回车间隔,并以#作为输入结束符;再请依次输入图中每条弧的两个顶点值,两个顶点值以空格作为间隔,每输入一组后进行换行,仍以#结束输入;最后一行为某顶点v。
好的,你想要输出有向连通图中某个顶点的入度。那么我们需要先构建出这个有向图,然后遍历所有边,统计出每个顶点的入度。
以下是一个示例代码实现:
```python
while True:
try:
vertices = []
arcs = []
while True:
vertex = input().strip()
if vertex == "#":
break
vertices.append(vertex)
while True:
arc = input().strip()
if arc == "#":
break
arc = arc.split()
arcs.append((arc[0], arc[1]))
v = input().strip()
# 构建邻接矩阵
n = len(vertices)
adj_matrix = [[0] * n for _ in range(n)]
for arc in arcs:
i = vertices.index(arc[0])
j = vertices.index(arc[1])
adj_matrix[i][j] = 1
# 统计入度
v_index = vertices.index(v)
indegree = 0
for i in range(n):
if adj_matrix[i][v_index] == 1:
indegree += 1
print(indegree)
except:
break
```
其中,输入格式要求多组数据,因此使用了一个无限循环,直到出现异常才退出循环。每次循环先读取顶点和边,然后构建邻接矩阵。最后统计某个顶点的入度并输出即可。
希望这个回答能够帮到你!
数据结构 C++实现 有向图的邻接表存储,并输出 顶点的出度和入度
下面是一个简单的 C++ 实现,使用邻接表存储有向图,并输出每个顶点的出度和入度:
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int V; // 图中顶点的数量
vector<vector<int>> adj; // 邻接表
public:
// 构造函数
Graph(int V) {
this->V = V;
adj.resize(V);
}
// 添加一条从 u 到 v 的边
void addEdge(int u, int v) {
adj[u].push_back(v);
}
// 输出每个顶点的出度和入度
void printDegree() {
for (int i = 0; i < V; i++) {
int out_degree = adj[i].size(); // 出度
int in_degree = 0; // 入度
// 计算入度
for (int j = 0; j < V; j++) {
for (auto k : adj[j]) {
if (k == i) {
in_degree++;
break;
}
}
}
cout << "顶点 " << i << " 的出度为 " << out_degree << ",入度为 " << in_degree << endl;
}
}
};
int main() {
// 创建图
Graph g(5);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(3, 4);
// 输出每个顶点的出度和入度
g.printDegree();
return 0;
}
```
输出结果如下:
```
顶点 0 的出度为 1,入度为 1
顶点 1 的出度为 1,入度为 1
顶点 2 的出度为 1,入度为 1
顶点 3 的出度为 1,入度为 0
顶点 4 的出度为 0,入度为 1
```