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

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

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

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

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

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