如果第一次閱讀本系列文檔請(qǐng)先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~

題目：

構(gòu)建一棵樹(shù)（Completing a Tree）

Given: A positive integer n (n≤1000) and an adjacency list corresponding to a graph on n nodes that contains no cycles.

所給：一個(gè)不大于1000的正整數(shù)n以及一個(gè)鄰接表，對(duì)應(yīng)一個(gè)有n個(gè)結(jié)點(diǎn)且無(wú)環(huán)的圖。

Return: The minimum number of edges that can be added to the graph to produce a tree.

需得：添加到圖中從而構(gòu)成樹(shù)的邊的最小數(shù)目。

?

測(cè)試數(shù)據(jù)

10

1 2

2 8

4 10

5 9

6 10

7 9

測(cè)試輸出

3

?

生物學(xué)背景

????????進(jìn)化樹(shù)是進(jìn)化生物學(xué)中用來(lái)表示物種進(jìn)化關(guān)系的圖表。從進(jìn)化樹(shù)中我們可以讀出物種間的進(jìn)化關(guān)系和距離。

?

數(shù)學(xué)背景

????????所謂無(wú)向圖就是邊沒(méi)有方向，相連兩個(gè)點(diǎn)可以互相抵達(dá)的圖。樹(shù)則是不含環(huán)的無(wú)向圖，結(jié)構(gòu)與自然界中的相對(duì)應(yīng)，如下所示：

????????無(wú)向圖頂點(diǎn)的邊數(shù)稱為度（degree），度為1的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，度大于1的結(jié)點(diǎn)為內(nèi)節(jié)點(diǎn)。

????????鄰接表是數(shù)組與鏈表相結(jié)合的存儲(chǔ)方法。本題中所給的鄰接表每行給出的兩個(gè)數(shù)字代表兩個(gè)結(jié)點(diǎn)由邊相連。

?

思路

????????由給出的示例數(shù)據(jù)可以畫出下圖：

????????從繪圖結(jié)果很容易看出，這十個(gè)結(jié)點(diǎn)形成了四“堆”：

只需要添加三條邊就可以變成一棵樹(shù)。

????????示例所給的數(shù)據(jù)比較簡(jiǎn)單，但對(duì)復(fù)雜數(shù)據(jù)，原理是相同的，請(qǐng)?jiān)斠?jiàn)代碼注釋。

代碼

f = open('input.txt', 'r')
lines = f.readlines()
f.close()

num = lines[0] # 存儲(chǔ)結(jié)點(diǎn)的數(shù)目
edges = lines[1:] # 存儲(chǔ)邊的關(guān)系
i = 1
nodes = []
while i <= int(num):
??? nodes.append(str(i)) # 用一個(gè)列表保存所有節(jié)點(diǎn)
??? i += 1

fedge = edges[0].replace('\n','') # 把鄰接表第一行取出來(lái)，作為第一“堆”的基礎(chǔ)
fedge = fedge.split(' ')
nodes.remove(fedge[0])
nodes.remove(fedge[1])
tree = [fedge] # tree用來(lái)存儲(chǔ)結(jié)點(diǎn)通過(guò)鄰接表存儲(chǔ)的關(guān)系形成的“堆”
flag = 1 # flag存儲(chǔ)現(xiàn)在tree里有幾“堆”
i = 1
while i < len(edges): # i遍歷鄰接表
??? edge = edges[i].replace('\n','')
??? edge = edge.split(' ')
??? if edge[0] in nodes:
??????? nodes.remove(edge[0]) # 每取出一個(gè)邊，就把形成邊的結(jié)點(diǎn)從結(jié)點(diǎn)列表中刪去
??? if edge[1] in nodes:
??????? nodes.remove(edge[1])
??? j = 0
??? tag = 0
??? note = []
??? while j < flag: # j用來(lái)遍歷各“堆”
??????? if edge[0] in tree[j]: # 如果這條邊的一個(gè)結(jié)點(diǎn)已經(jīng)在其中一個(gè)“堆”里
??????????? tree[j].append(edge[1]) # 把這個(gè)邊加入這一“堆”
??????????? tag += 1
??????????? note.append(j) # note存儲(chǔ)這個(gè)結(jié)點(diǎn)在哪個(gè)“堆”
??????????? j += 1
??????? elif edge[1] in tree[j]:
??????????? tree[j].append(edge[0])
??????????? tag += 1
??????????? note.append(j)
??????????? j += 1
??????? else: # 如果不在這一“堆”里，j加一，以查找下一“堆”
??????????? j += 1
??? if tag == 0: # 如果在之前存在的“堆”里都沒(méi)有這條邊
??????? tree.append(edge)
??????? flag += 1 # 添加一個(gè)新的“堆”
??? if tag == 2: # 如果兩個(gè)結(jié)點(diǎn)各在兩“堆”中，說(shuō)明這兩個(gè)“堆”可以合并
??????? flag -= 1
??????? tree[note[0]].extend(tree[note[1]])
??????? tree.remove(tree[note[1]]) # 合并兩“堆”并刪去其中一個(gè)
??????? tree[note[0]].remove(edge[0])
??????? tree[note[0]].remove(edge[1]) # 刪去由合并導(dǎo)致的重復(fù)結(jié)點(diǎn)

??? i += 1

print(tree)
lennodes = len(nodes) # 記錄現(xiàn)在結(jié)點(diǎn)列表中還有幾個(gè)結(jié)點(diǎn)，每個(gè)都相當(dāng)于一個(gè)單獨(dú)的“堆”
sum = (flag - 1) + lennodes # “堆”的數(shù)量減去一即為需要添加的邊的數(shù)量
print(sum)

?