在 Python 中找出给定图中特殊类型的子图的程序
假设我们有一种特殊类型的图，它有两种类型的顶点，分别称为头和脚。该图只有一个头部，并且有 k 条边将头部连接到每只脚。因此，如果给定一个无向、未加权的图；我们将不得不在图的顶点不相交子图中找出这些特殊类型的图。如果两个图没有共同的顶点，则称它们是顶点不相交的。
所以，如果输入像
节点数 (n) = 5，英尺数 (t) = 2，那么输出将为 5。
可以有 5 个这样的特殊图，它们是给定图的顶点不相交子图。
示例
让我们看看以下实现以更好地理解 -
def solve(n, t, edges):G = [[] for _ in range(n + 1)]
for item in edges:
s, d = map(int, item)
G[s].append(d)
G[d].append(s)
visit = {}
for i in range(n):
v = G[i]
if len(v) == 1:
s = v[0]
if s not in visit:
visit[s] = [i]
else: visit[s].append(i)
elif len(v) == 0:
n -= 1
tmp = 0
for k in visit:
x = len(visit[k])-t
if x > 0:
tmp += x
return n - tmp
print(solve(6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]))
输入
6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]输出结果
5
以上是 在 Python 中找出给定图中特殊类型的子图的程序 的全部内容， 来源链接： utcz.com/z/363244.html
