關(guān)節(jié)點(diǎn)與重連通圖

關(guān)節(jié)點(diǎn)與重連通圖第1頁，課件共11頁，創(chuàng)作于2023年2月關(guān)節(jié)點(diǎn)如果一個(gè)連通圖在刪除了某個(gè)頂點(diǎn)u以及與u相連接的邊之后，變成了非連通圖，這個(gè)頂點(diǎn)u就稱為關(guān)節(jié)點(diǎn)下圖中的頂點(diǎn)2和頂點(diǎn)6就是關(guān)節(jié)點(diǎn)5342167第2頁，課件共11頁，創(chuàng)作于2023年2月重連通圖一個(gè)不含關(guān)節(jié)點(diǎn)的連通圖稱為重連通圖對(duì)于重連通的無向圖來說，每對(duì)頂點(diǎn)之間至少存在兩條路徑連通圖可以用來表示通信網(wǎng)絡(luò)系統(tǒng)。為了提高系統(tǒng)的穩(wěn)定性，網(wǎng)絡(luò)中不應(yīng)該有關(guān)節(jié)點(diǎn)。第3頁，課件共11頁，創(chuàng)作于2023年2月關(guān)節(jié)點(diǎn)的判定如何來判定一個(gè)連通圖中是否有關(guān)節(jié)點(diǎn)呢？通過考察連通圖的深度優(yōu)先生成樹，可以得出解決此問題的一個(gè)方法第4頁，課件共11頁，創(chuàng)作于2023年2月關(guān)節(jié)點(diǎn)的判定對(duì)于左上圖，若從頂點(diǎn)2開始做深度優(yōu)先遍歷，可以得到一棵深度優(yōu)先生成樹，其中的實(shí)線邊構(gòu)成這個(gè)深度優(yōu)先樹，虛線邊表示回邊53421672364751第5頁，課件共11頁，創(chuàng)作于2023年2月關(guān)節(jié)點(diǎn)在深度優(yōu)先生成樹中的某個(gè)頂點(diǎn)u，要么是根，要么不是根先討論頂點(diǎn)u是生成樹的根u是關(guān)節(jié)點(diǎn)的充要條件是：u有兩棵或者兩棵以上的子樹。判定方法：遍歷過程中做訪問標(biāo)記。從頂點(diǎn)u相鄰的某個(gè)頂點(diǎn)做遍歷，當(dāng)遍歷結(jié)束時(shí)，所有頂點(diǎn)都做了訪問標(biāo)記，則說明u只有一棵子樹，不是關(guān)節(jié)點(diǎn)，否則說明u至少有兩棵子樹，是關(guān)節(jié)點(diǎn)第6頁，課件共11頁，創(chuàng)作于2023年2月關(guān)節(jié)點(diǎn)另一種情況，u不是深度遍歷的根結(jié)點(diǎn)假設(shè)v是u的一個(gè)孩子，則u是關(guān)節(jié)點(diǎn)的充要條件是：在v或者v的子孫結(jié)點(diǎn)和u的祖先結(jié)點(diǎn)之間不存在任何回邊如何來判定這個(gè)充要條件？引入深度優(yōu)先數(shù)和最低深度優(yōu)先數(shù)的概念第7頁，課件共11頁，創(chuàng)作于2023年2月深度優(yōu)先數(shù)深度優(yōu)先數(shù)是指在按照某種深度優(yōu)先遍歷的過程中，依次給每個(gè)頂點(diǎn)標(biāo)個(gè)號(hào)，用DFN[u]表示按照右圖從頂點(diǎn)1開始做

遍歷，每個(gè)頂點(diǎn)的DFN[i]

是多少呢？2364751第8頁，課件共11頁，創(chuàng)作于2023年2月最低深度優(yōu)先數(shù)最低深度優(yōu)先數(shù)用L[u]表示，定義如下：

DFN[u]min{L[v]|在生成樹中，v是u的孩子}min{DFN[v]|在生成樹中，v是u的雙親或（u，v）是一條回邊}L[u]=min第9頁，課件共11頁，創(chuàng)作于2023年2月關(guān)節(jié)點(diǎn)在u不是深度優(yōu)先生成樹的根的前提條件下，若u存在一個(gè)孩子v，使得DFN[u]<=L[v]成立，則u是關(guān)節(jié)點(diǎn)第10頁，課件共11頁，創(chuàng)作于2023年2月練習(xí)關(guān)節(jié)點(diǎn)（key.c/key.in/key.out）

在一個(gè)無向連通圖中，輸入這個(gè)連通圖的鄰接矩陣形式，判斷這個(gè)無向圖中是否存在關(guān)節(jié)點(diǎn)，如果不存在，則輸出“safe”，如果存在，則按照頂點(diǎn)編號(hào)由小到大輸出關(guān)節(jié)點(diǎn)

輸入文件第一行為n，表示有n個(gè)頂點(diǎn)，接下來是個(gè)n×n的矩陣

輸出文件一行，如果無關(guān)節(jié)點(diǎn)，輸出“safe”，如果有，則依次輸出關(guān)節(jié)點(diǎn)編號(hào)，每個(gè)關(guān)節(jié)點(diǎn)中間用一個(gè)空格隔開

樣例輸入