设有向图G,试找出图中出度为0的顶点有多少个? 输入格式: 输入数据有多组,每组数据第一行为一个正整数vertexnum( 0<vertexnum<500 ),代表G的顶点数目,接下来是有向图G的邻接矩阵。
时间: 2024-03-13 08:42:26 浏览: 21
好的,我知道你的问题了。这是一个求有向图中出度为0的顶点个数的问题。
那么解决这个问题的思路是,遍历每个顶点,统计其出度是否为0。如果为0,则计数器加1。
以下是一个示例代码实现:
```python
while True:
try:
vertexnum = int(input())
matrix = []
for i in range(vertexnum):
matrix.append(list(map(int, input().split())))
count = 0
for i in range(vertexnum):
if matrix[i].count(1) == 0:
count += 1
print(count)
except:
break
```
其中,输入格式要求多组数据,因此使用了一个无限循环,直到出现异常才退出循环。每次循环读取顶点数和邻接矩阵,然后遍历每个顶点,统计出度为0的顶点个数。最后输出即可。
希望这个回答能够帮到你!
相关问题
数据结构(Python) 设有向图G,试找出图中出度为0的顶点有多少个? 输入格式: 输入数据有多组,每组数据第一行为一个正整数vertexnum( 0<vertexnum<500 ),代表G的顶点数目,接下来是有向图G的邻接矩阵。 输出格式: 对于每组数据,请在一行里输出出度为0的顶点个数。 输入样例: 在这里给出两组输入。例如: 3 0 0 1 0 0 0 1 0 0 5 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 输出样例: 在这里给出相应的输出。例如: 1 3
以下是 Python 代码实现:
```python
while True:
try:
n = int(input())
matrix = []
for i in range(n):
row = list(map(int, input().split()))
matrix.append(row)
out_degree_zero = 0
for i in range(n):
out_degree = 0
for j in range(n):
out_degree += matrix[i][j]
if out_degree == 0:
out_degree_zero += 1
print(out_degree_zero)
except:
break
```
解释如下:
- 首先进入一个死循环,不断地读入数据,直到遇到异常结束程序。
- 读入顶点数 n,然后读入邻接矩阵。
- 用 out_degree_zero 记录出度为 0 的顶点个数,初始化为 0。
- 对于每个顶点 i,遍历其邻接矩阵的一行,将其所有出边的权值相加,得到 out_degree。
- 如果 out_degree 等于 0,说明顶点 i 没有出边,即出度为 0,将 out_degree_zero 加 1。
- 最后输出 out_degree_zero,即出度为 0 的顶点个数。
用python编码,设有向图G,试找出图中出度为0的顶点有多少个? 输入格式: 输入数据有多组,每组数据第一行为一个正整数vertexnum( 0<vertexnum<500 ),代表G的顶点数目,接下来是有向图G的邻接矩阵。 输出格式: 对于每组数据,请在一行里输出出度为0的顶点个数。 输入样例: 在这里给出两组输入。例如: 3 0 0 1 0 0 0 1 0 0 5 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 输出样例: 在这里给出相应的输出。例如: 1 3
以下是Python3代码实现:
```python
while True:
try:
n = int(input())
a = []
for i in range(n):
a.append(list(map(int, input().split())))
indegree = [0] * n
for i in range(n):
for j in range(n):
indegree[j] += a[i][j]
count = 0
for i in range(n):
if indegree[i] == 0:
count += 1
print(count)
except:
break
```
算法思路:对于每个顶点,遍历其对应的每一列,如果有对应的行元素为1,则该顶点的入度+1。统计完所有顶点的入度后,再遍历所有顶点,统计出度为0的顶点个数即可。