在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：一个新的映射
• 对于i在范围0到n之间，操作如下：
  • 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