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

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

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

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

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

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

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