國家集訓隊作業(yè)sgu413解題報告

1、SGU413 Berland Divi解題問題簡述：給出一個頂點數為偶數的連通圖，將其分成若干不相交的子圖，使得每個子圖都是一棵頂點數大于 1 的樹。(題目沒對無解時如何輸出做出解釋)問題分析：本題要將一個圖分解，那么如何分解?如何保證一個子圖是一棵樹呢？這都是非常麻煩的事情。另外圖的頂點是偶數，這個條件有什么用呢？如果頂點數為奇數，顯然一個長度為 3 的環(huán)就是無解的，那么偶數是否就意味著一定有解呢？讓一步步分析。直接把圖分解是比較的，可以嘗試利用圖的生成樹的某些性質，找出圖上已有的樹。比較容易想到的當然就是簡單的 DFS 生成樹了。那么DFS 生成樹有什么性質呢?不難發(fā)現生成樹上的任意節(jié)點和

2、其兒子組成的子圖在原圖中肯定是一棵樹。因為兒子之間是不會有邊相連的，否則由 DFS 的性質，他們不可能成為兄弟。這樣不難得出一個貪心的算法，利用把任意節(jié)點和其兒子的子圖在原圖中都是一棵樹的性質，可以從 DFS 樹的葉子開始往上分組，把當前節(jié)點和未分組的兒子分為同一組。如果不存在未分組的兒子則當前節(jié)點標記為未分組。下圖是一個例子：相同顏色的分為一組顯然這個算法存在一個缺陷，就是根節(jié)點可能沒有分進任何一組。如下圖左邊所示：這該如何解決呢？實際上該算法成功與否與DFS 生成樹的形態(tài)有很大關系。對于上圖的情況，如果把原來根紅色的兒子作為新根就能得到右圖的可行可以采用枚舉根甚至隨機改變 DFS 順序的方

3、法來多次求解。而對解。因此于SGU 的數據，只需要枚舉根就可以Accept 了。這個算法十分簡潔，而且正確率極高，時間復雜度為 O(NM)。但這樣的算法并不完美，而且沒有利用到 N 為偶數的性質，分析。還需進一步算法改進：上文算法只在根節(jié)點處會出現問題，就從這下手。首先還是按照上文的算法遍歷圖，如果根節(jié)點已經在某組內則已得到可行解，否則先嘗試把根添加到某一組內，如果根只與該組中的一個點相連則直接添加，同樣得到一組可行解。而如果無法添加，為得到可行解勢必要改變原有的分組方式。并且要注意到此時任一組與根之間至少有兩條邊。讓先來根節(jié)點兒子所在的組。如果該組只有兩個點，則此時根必然與這兩個點形成一個長

4、度為 3 的環(huán)，無法通過調整得到可行解。而如果該組不止兩個節(jié)點，由于每一組都是一個父親帶上若干個兒子的形式，必然存在某個兒子與根有邊相連，這樣把它和根分成一組，其他分組方式不變就可行解。下圖是一個例子：實線為 DFS 樹邊，虛線為原圖的非樹邊。那么當所有根的兒子所在的組都只有兩個點時，又該怎么辦呢?這時就要利用 N 為偶數的條件了。顯然根以及根的兒子所在的組的所有節(jié)點的總數為奇數，那么剩下的節(jié)點個數也為奇數。即下圖所有綠色三角形(每個三角形為一棵去掉根的)中的點的個數為奇數。由奇偶分析知，必然有一個的三角形節(jié)點數為的奇數(下圖中用深綠色表示)，加上其的根便總共有偶數個節(jié)點，而且這棵是連通的。這樣不就和原問題的條件相同了嗎?因此可以把這部分遞歸求解，而把多余的那個節(jié)點和根分為同一組，其他不變即可。按照上文的算法，每次要么小的子問題，所以到最后已經得到可行解，要么得到一個規(guī)模減會得出正確解。而且遞歸最多進行 N/2 次