問題：關節點和重連通分量

題目描述
假若在刪去頂點v以及和v相關聯的各邊之后，將圖的一個連通分量分割成兩個或兩個以上的連接分量，則稱頂點v為該圖的一個關節點。一個沒有關節點的連通圖稱為重連通圖。在重連通圖上，任意一對頂點之間至少存在兩條路徑，則在刪去某個頂點以及依附于該頂點的各邊時也不會破壞圖的連通性。
利用深度優先搜索可以求出圖的關節點，并由此可以判斷圖是否是重連通的。
通過修改深度優先搜索遍歷的算法便可以得到求關節點的算法，其算法描述如下：
在本題中，讀入一個無向圖的鄰接矩陣（即數組表示），建立無向圖并按照以上描述中的算法求出所有的關節點，并輸出這些關節點。

輸入 :
輸入的第一行包含一個正整數n，表示圖中共有n個頂點。其中n不超過50。
以后的n行中每行有n個用空格隔開的整數0或1，對于第i行的第j個整數，如果為1，則表示第i個頂點和第j個頂點有直接連接，0表示沒有直接連接。當i和j相等的時候，保證對應的整數為0。
輸入保證鄰接矩陣為對稱矩陣，即輸入的圖一定是無向圖，且保證圖中只有一個連通分量。
輸出:
第一行有一個整數x，即圖中關節點的個數。
第二行輸出x個整數，表示所有關節點的頂點編號，請按照編號從小到大的順序輸出。每個整數后輸出一個空格，并請注意行尾輸出換行。
樣例輸入
4
01 1 1
1 0 0 0
1 0 0 0
1 0 0 0
樣例輸出
1
0
提示
在本題中，需要掌握圖的深度優先遍歷的方法，并需要掌握通過深度優先搜索求得圖中關節點的算法。通過生成深度優先生成樹可以得出兩類關節點的特性：

• 若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關節點。

• 若生成樹中某個非葉子頂點v，其某棵子樹的根和子樹中的其他結點均沒有指向v的祖先的回邊，則說明v是關節點。

注意以上兩點特性，就可以成功的通過深度優先搜索遍歷的算法得出圖中的關節點了。

代碼展示：

n = int(input()) visited=[0]*n#訪問列表，用于判斷節點訪問狀態 low=[1000000]*n#初始化權值列表 count=0 end_ans=[]#結果列表 def DFS(G,v0):global count,visited,low,n,end_anscount+=1visited[v0]=min=countfor i in range(0,n):if G[v0][i]!=0:#讀入鄰接節點if visited[i]==0:DFS(G,i)if low[i]<min:min=low[i]if low[i]>=visited[v0]:end_ans.append(v0)else:if visited[i]<min:min=visited[i]low[v0]=mindef FindArticul(G):global visited,count,n,end_ansvisited[0]=1count=1for i in range(1,n):if G[0][i]!=0:DFS(G,i)if count<n:end_ans.append(0)while i<n:if G[0][i]!=0 and visited[i]==0:DFS(G,i)i+=1return if __name__=='__main__':G=[]#無向連通圖-鄰接矩陣形式for i in range(0, n):res = input()ans = res.split(' ')G.append([int(i) for i in ans])FindArticul(G)print(len(end_ans))end_ans.sort()for i in end_ans:print(i,end=' ')print()

總結

以上是生活随笔為你收集整理的关节点和重连通分量，trajan算法实现（python）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。