資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告