数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：查找给定图中的特殊子图
假设我们有一种特殊的图，它具有两种类型的顶点，分别命名为头部和尾部。该图只有一个头部，并且有k条边将头部连接到每个尾部。因此，如果给定一个无向、无权图；我们将必须在图的顶点不相交的子图中找出这些特殊类型的图。如果两个图没有公共顶点，则称它们为顶点不相交。
因此，如果输入如下所示：
节点数 (n) = 5，尾部数 (t) = 2，则输出将为5。
可以有5个这样的特殊图，它们是给定图的顶点不相交子图。
为了解决这个问题，我们将遵循以下步骤：
- G := 一个新的列表，包含n+1个空列表
- 对于edges中的每个项目，执行以下操作：
- s := item[0]
- d := item[1]
- 在G[s]的末尾插入d
- 在G[d]的末尾插入s
- visit := 一个新的映射
- 对于范围从0到n的i，执行以下操作：
- v := G[i]
- 如果v的大小与1相同，则
- s := v[0]
- 如果s不在visit中，则
- visit[s] := [i]
- 否则，
- 在visit[s]的末尾追加i
- 否则，当v的大小与0相同时，则
- n := n - 1
- tmp := 0
- 对于visit中的每个k，执行以下操作：
- x := visit[k]的大小 - t
- 如果x > 0，则
- tmp := tmp + x
- 返回n - tmp
示例
让我们看看下面的实现，以便更好地理解：
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
更新于：2021年10月6日
421 次浏览
广告