圖論算法-割點(diǎn)、割邊應(yīng)用

圖論算法－割點(diǎn)、割邊~apieceofcake~引題我們常常碰到一些求刪某條邊使其圖不連通，或點(diǎn)。如ZJ.PTSC2004的《嗅探器》，如KOJ上的《消息不可走漏》，雖然我們都可以用暴力來(lái)解決，但是這個(gè)時(shí)間復(fù)雜平方級(jí)別的，一但數(shù)據(jù)范圍擴(kuò)大，這個(gè)就無(wú)法解決了。其實(shí)這個(gè)是有線性算法。概念如果一張無(wú)向連通圖，在刪掉某些點(diǎn)集后這張圖就不連通，而刪掉這個(gè)集合的任意一個(gè)真子集，這張圖任就是連通的，那么就稱這個(gè)點(diǎn)集為點(diǎn)割集，如果一個(gè)結(jié)點(diǎn)就是點(diǎn)割集，那么就稱這個(gè)結(jié)點(diǎn)為割點(diǎn)概念如果一張無(wú)向連通圖，在刪掉某些邊集后這張圖就不連通，而刪掉這個(gè)集合的任意一個(gè)真子集，這張圖任就是連通的，那么就稱這個(gè)點(diǎn)集為邊割集，如果一個(gè)結(jié)點(diǎn)就是點(diǎn)割集，那么就稱這個(gè)結(jié)點(diǎn)為割邊或橋First首先我們必須明白一點(diǎn)，關(guān)於圖的DFS的性質(zhì)，我們對(duì)圖進(jìn)行DFS遍歷，DFS本身是沒(méi)有什么作用，只用來(lái)求連通塊，而我們利用的是DFS的遍歷順序。DFS遍歷出來(lái)的一棵樹(shù)滿足一個(gè)特點(diǎn)：對(duì)于一個(gè)結(jié)點(diǎn)的任意兩個(gè)以其兒子結(jié)點(diǎn)為根的子樹(shù)，必須通過(guò)這個(gè)結(jié)點(diǎn)或者其祖先才能連通，也就是說(shuō)，在刪掉這個(gè)結(jié)點(diǎn)后，任意兩棵以其兒子為根的子樹(shù)都不互相連通。這個(gè)很顯然，因?yàn)閷?duì)于一棵子樹(shù)，如果與其連通，那么就都會(huì)遍歷到，不然就回溯至其祖先。算法那么在DFS的時(shí)候，我們紀(jì)錄每個(gè)兒子子樹(shù)，與其相連的最高的祖先的層號(hào)，如果這個(gè)層號(hào)>=其父親的層號(hào),那么刪掉這個(gè)父親結(jié)點(diǎn)后這棵子樹(shù)將于其祖先不連通.如果這個(gè)層號(hào)>其父親的層號(hào),那么刪掉這條連接父親的邊,那么這棵子樹(shù)將于其祖先不連通.算法那么這個(gè)算法也就出來(lái)了,只需在DFS時(shí)加入求和其相連的最高祖先的語(yǔ)句就行了消息不可走漏(KOJ1047)Description瑪莉得知公主被虜走的消息，決定前去營(yíng)救，所以這個(gè)消息堅(jiān)決不能夠被敵人知道了，因?yàn)閿橙艘坏弥?，告知了每個(gè)堡壘后，營(yíng)救工作一定會(huì)非常困難的！！

瑪莉竊取了一分地圖，里面記載了敵人的n座堡壘，某些堡壘之間修筑了公路。任意兩個(gè)堡壘都可以通過(guò)公路直接或者間接到達(dá)?，斃虬l(fā)現(xiàn)有些公路被毀壞之后會(huì)造成某兩個(gè)城市之間無(wú)法互相通過(guò)公路到達(dá)。只要炸掉這樣的一條公路，瑪莉就可以完成他的第一步救援計(jì)劃了。但是，要在短時(shí)間內(nèi)找出來(lái)，這是個(gè)多么難的問(wèn)題呀，所以現(xiàn)在瑪莉求助于你，希望你能夠通過(guò)編程，在１秒中內(nèi)找出這樣的公路來(lái)。

分析這題是一題割邊的應(yīng)用,當(dāng)然用復(fù)雜度再高點(diǎn)的算法也可以.這題的算法就是割邊,是練習(xí)割邊的基礎(chǔ)題.嗅探器(PTSC.ZJ04)某軍搞信息對(duì)抗實(shí)戰(zhàn)演習(xí).紅軍成功地侵入了藍(lán)軍的內(nèi)部網(wǎng)絡(luò).藍(lán)軍共有兩個(gè)信息中心.紅軍計(jì)劃在某臺(tái)中間服務(wù)器上安裝一個(gè)嗅探器,從而能夠偵聽(tīng)到兩個(gè)信息中心互相交換的所有信息.但是藍(lán)軍的網(wǎng)絡(luò)相當(dāng)?shù)凝嫶?數(shù)據(jù)包從一個(gè)信息中心傳到另一個(gè)信息中心可以不止有一條通路.現(xiàn)在需要你盡快地解決這個(gè)問(wèn)題.應(yīng)該把嗅探器安裝在哪個(gè)中間服務(wù)器上才能保證所有的數(shù)據(jù)包都能被捕獲?嗅探器分析這題顯然是求割點(diǎn),但是這個(gè)割點(diǎn)有些不同,這個(gè)點(diǎn)割掉只能使a,b不連通,那么怎么做呢?顯然這題可以用暴力枚舉來(lái)實(shí)現(xiàn),復(fù)雜度雖然大,但是這題的范圍不大,所以還是可以做的分析那怎么用割點(diǎn)來(lái)實(shí)現(xiàn)呢?很顯然問(wèn)題要求的點(diǎn)一定是這張圖的割點(diǎn),但是割點(diǎn)并不都是這個(gè)問(wèn)題要求的點(diǎn).我們通過(guò)觀察割點(diǎn)算法,如果紀(jì)錄在當(dāng)前子樹(shù)是否有a,或者b.那么這些點(diǎn)也就很容易描述了:這個(gè)點(diǎn)是割點(diǎn),且AXorB分析所以在實(shí)現(xiàn)時(shí)只要在判斷是否是割點(diǎn)時(shí)加入這個(gè)判斷語(yǔ)句就可以了.CEOI2005(關(guān)鍵網(wǎng)線問(wèn)題

)(CriticalNetworkLines)Inputfile:net.in100pointsOutputfile:net.outTimelimit:3secSourcecode:net.pas/.c/.cppMemorylimit:64MB問(wèn)題描述考慮這樣一個(gè)通訊網(wǎng)絡(luò)，它由一些結(jié)點(diǎn)和連接結(jié)點(diǎn)之間的雙向網(wǎng)線組成。已知該連通網(wǎng)絡(luò)的每對(duì)結(jié)點(diǎn)之間都存在一條信息流通網(wǎng)路。一些結(jié)點(diǎn)向所有結(jié)點(diǎn)（包括自己）提供A服務(wù)，同時(shí)一些結(jié)點(diǎn)也向所有結(jié)點(diǎn)提供B服務(wù)。同一個(gè)結(jié)點(diǎn)有可能同時(shí)提供這兩種服務(wù)。每個(gè)結(jié)點(diǎn)都應(yīng)當(dāng)能得到這兩種服務(wù)。如果有一根網(wǎng)線出現(xiàn)問(wèn)題，可能導(dǎo)致某個(gè)結(jié)點(diǎn)無(wú)法獲得某個(gè)服務(wù)，具備這種性質(zhì)的網(wǎng)線就稱為關(guān)鍵網(wǎng)線。任務(wù)目標(biāo)編一段程序，找出關(guān)鍵網(wǎng)線數(shù)（TaskA）以及連接這些網(wǎng)線的兩端結(jié)點(diǎn)（結(jié)點(diǎn)對(duì)）（TaskB）。輸入數(shù)據(jù)文件net.in的第一行包含4個(gè)整數(shù)：總的結(jié)點(diǎn)數(shù)N(1≤N≤100000)，連接的網(wǎng)線數(shù)

M(1≤M≤1000000)，提供A服務(wù)的結(jié)點(diǎn)數(shù)K(1≤K≤N)，提供B服務(wù)的結(jié)點(diǎn)數(shù)L(1≤L≤N)。第二行是K個(gè)整數(shù)，標(biāo)明提供A服務(wù)的結(jié)點(diǎn)。。輸入文件第三行是L個(gè)整數(shù)，標(biāo)明提供B服務(wù)的結(jié)點(diǎn)。接下來(lái)的M行表示網(wǎng)線的連接位置，每行有兩個(gè)整數(shù)pq(1≤p,q≤N,p≠q)，是網(wǎng)線兩端的結(jié)點(diǎn)。任意兩個(gè)結(jié)點(diǎn)之間，最多有一條網(wǎng)線相連。輸出文件文件net.out的第一行是關(guān)鍵網(wǎng)線的數(shù)目S（TaskA）。接下來(lái)的S行各含一對(duì)整數(shù)pq(1≤p,q≤N)，分別定義了一條關(guān)鍵網(wǎng)線（TaskB）關(guān)鍵網(wǎng)線可以按任意順序輸出。每一條關(guān)鍵網(wǎng)線的兩個(gè)端點(diǎn)也可按任一順序輸出。Examplenet.in

net.out910342454983124123421556676879873325679分析這題,很顯然是求橋,但是這個(gè)橋有不同之處,并不是只要圖不連通就可以了.由題意可知這些邊一定是橋,但是橋不一定是這些邊.要是某些點(diǎn)得不到某種服務(wù),那么就是要求在其連通塊中該沒(méi)有服務(wù)的