【正文】 space, 3 ≤ n ≤10 000, 0 ≤ m ≤ n ≤ 3. Integer n is the number of vertices of a polygon and integer m is the number ofits diagonals, respectively.The second of those lines contains exactly 2(m+n) integers separated by single spaces. Those are ends of all sides and some diagonals of the polygon. Integers aj。 n, . the numbers of subsequent vertices on the border of the polygon from the ith data set。 2。reads the description of sides and diagonals given to Bob by Alice,s say Alice and Bob. Alice draws an nvertex convex polygon and numbers its vertices with integers 1。 reads from the text file the map of ski tracks, 由于a和b不在同一個域中，因此路徑1（）和路徑2（）之間至少存在另一條路徑3，這條路徑要么是從路徑1連到路徑2，要么是從路徑2連到路徑1。3）a是域F1右邊的那條路徑，b是域F2左邊的那條路徑。2．：反設(shè)最長反鏈A中存在兩條相鄰的邊不再同一個域中，令這兩條邊為a和b，且a在b的左邊。令x是極小元，而y是極大元且x ≤ y(x可以等于y)。因為若Ci+中的極小元不是ai而是x，那么根據(jù)A+的定義，存在一個aj ≤ x，則有aj ≤ x ≤ ai，這與A是反鏈矛盾，所以ai是極小元。因為A+、A?中的元素個數(shù)小于n，根據(jù)歸納假設(shè)，A+、A?一定能夠劃分成m條鏈。反設(shè)存在一個x在中，而不在P中。反設(shè)存在一個x在中，而不屬于A。因此A?≠P，A?中的元素個數(shù)小于P的元素個數(shù)n。現(xiàn)定義，即A?中任一個元素x在A中能找到一個元素ai，使得x ≤ ai。因此只需要證明一定存在M小于等于m。本文或許沒有完美的概括圖論的基本思想和方法，僅僅是作者對圖論的一點理解和想法。例題二的解析過程，不僅僅體現(xiàn)了圖論的基本思想，同時還展現(xiàn)了算法與數(shù)據(jù)結(jié)構(gòu)的完美結(jié)合，以及算法的優(yōu)化思想。同時文章中還介紹了三種解決問題的方法：定義法、分析法和綜合法。綜合法的運用需要有全局觀，要能夠發(fā)現(xiàn)最具代表性的模型特性。算法三體現(xiàn)了一種綜合思想，不是單獨考慮每一條邊的連通性，而是從全局考慮，發(fā)現(xiàn)了多邊形的邊和對角線在DFS樹中的區(qū)別。而在算法二的設(shè)計過程中，發(fā)現(xiàn)了每次刪除多邊形的一個角時仍是一個多邊形，也就是找到了子問題的相似性，這樣就可以不斷地縮小問題的規(guī)模。考慮上述四種情況已經(jīng)能夠判斷圖G中所有邊的性質(zhì)了。令x是與v直接相連的祖先結(jié)點中dfn值最小的一個結(jié)點，那么(x, v)一定是原始多邊形的邊（證明同情況1中的分析）。2．v的兒子數(shù)為1，且u為DFS樹的根：易知，(u, v)一定是多邊形的邊。令y為異于x和u，而與v相連的點。令x是與v直接相連的祖先結(jié)點中dfn值最小的一個結(jié)點，那么(x,v)一定也是原始多邊形的邊。接下來分情況討論如何用dfn和low函數(shù)判斷一條邊的性質(zhì)：考慮DFS樹上的一條邊(u, v)，其中u是v的父親結(jié)點。由于是深度優(yōu)先遍歷，那么在這兩部分剩下的點中，有一部分的點會被優(yōu)先遍歷到。算法二的時間復(fù)雜度已經(jīng)十分低了。7． 遍歷圖C得到原始多邊形頂點的標(biāo)號順序。如果邊(v1,v2)不存在，則添加一條虛邊(v1,v2)，v1和v2的度數(shù)不變；否則將v1和v2的度數(shù)減一。若不是虛邊，用并查集檢查其是否為對角線。初始化附加圖C。綜上所述，在這些桶中查找和調(diào)整一個度為2的結(jié)點所需的時間復(fù)雜度為O(1)。在每個桶中用雙向鏈接表存儲下不同的結(jié)點。這樣在保證查找復(fù)雜度仍然是O(1)的情況下，存儲空間比鄰接矩陣小了很多。值得注意的是，當(dāng)圖C中已經(jīng)有了n 1條邊時，剩下的那條邊會被判斷成對角線，但此時已經(jīng)能夠確定多邊形頂點的標(biāo)號序列了。一條邊（Hi, Hj）當(dāng)且僅當(dāng)成為某個多邊形的邊時，它才有可能被移除。如此反復(fù)，直到圖中不存在度為2的點。圖G’和圖G具有同樣的性質(zhì)，因此也至少存在一個度為2的點，令其為Hj。而(Hi1, Hi)和(Hi, Hi+1)兩條邊都是多邊形的邊，將這兩條邊添加到一個附加圖C中（附加圖C一開始只有n個頂點，對應(yīng)著多邊形的頂點，頂點之間沒有邊相連）。將以u為頂點的三角形從多邊形上刪除，剩下的圖形仍然是一個多邊形。所以總的復(fù)雜度為O(n2)。如果a能夠到達(dá)圖G’中的其它點，那么就說明圖G’是連通的，(u, v)是多邊形的邊；否則，圖G’不連通，(u, v)是多邊形的對角線。 利用邊的連通性，如果一條邊是對角線，那么將對角線的兩個端點從圖G中刪除，圖G一定會變成兩個互不可達(dá)的連通分塊；而如果一條邊是多邊形上的邊，那么將這條邊的兩個端點刪除，圖G將仍然是連通的。因此哈密頓回路上的邊都是由多邊形上的邊組成，而多邊形的邊只有n條，可知哈密頓回路也就只有一條。而且十分明顯的是，圖G是一個平面圖，根據(jù)歐拉公式，圖中邊的數(shù)量級為O(n)。鮑比必須猜出頂點順（逆）時針的標(biāo)號序列，任意一個符合條件的序列即可。例二：愛麗絲和鮑勃（ACM Central European Programming Contest 2001 Problem A : Alice and Bob）題目描述：愛麗絲和鮑勃在玩一個游戲。圖論模型更多的是思考的一種過渡，使思路變得清晰，就像一座燈塔，指引你到成功的彼岸。正所謂“磨刀不誤砍柴功”，在設(shè)計算法之前，選擇一個正確的圖論模型往往能夠起到事半功倍的效果，不僅能降低算法設(shè)計的難度，還使設(shè)計出的算法簡單高效。 小結(jié)方法一利用網(wǎng)絡(luò)流模型直接的體現(xiàn)了原題的網(wǎng)絡(luò)（有向無環(huán)）特性，解法具有一般性，但是沒有充分的體現(xiàn)出原題的平面圖性質(zhì)。 黑色end計算上述算法的復(fù)雜度：，復(fù)雜度為O(|E|)；，并且進(jìn)行遞推求解。 vvh 223。擴(kuò)展它的父結(jié)點用pre記錄。 相應(yīng)的算法設(shè)計可以用DFS深度優(yōu)先遍歷實現(xiàn)平面圖中域的尋找。設(shè)f(x)表示在邊x左邊的平面區(qū)域中以x結(jié)尾的最長反鏈的長度。所謂的域，是由從一個點到另一個點（一個是極高點，一個是極低點）的兩條不同路徑（兩條路徑?jīng)]有公共邊）圍成的一個曲面，在這個曲面里沒有其他的點和邊（如圖23所示），記作F。如何求解最長的反鏈呢？事實上，這和原題給出的平面圖有很大關(guān)系，接下來，返回到原圖上繼續(xù)討論。在E中，有m = M。當(dāng)且僅當(dāng)va = ub時，有a ≤c b。 構(gòu)筑原問題的偏序集模型有了上文有關(guān)偏序集的概念，不難搭建出原問題的偏序集模型：令原圖表示的偏序集為(X, ≤)，而新構(gòu)造的偏序集為(E, ≤)。鏈：鏈?zhǔn)荅的一個子集C，在偏序關(guān)系≤下，它的每一對元素都是可比的，即C是E的一個全序子集。若a c b，那么a和b之間連一條邊。若X是一個有限集，由偏序集的傳遞性易知，任一個偏序關(guān)系都可以用多個覆蓋關(guān)系表示出來，也就是說可以用覆蓋關(guān)系有效的表示偏序關(guān)系。集合X上的一個偏序關(guān)系R，如果使得X中的任意一對元素都是可比的，那么該偏序R就是一個全序。若有a ≤ b，且a ≠ b，那么就記作a b或者b a。b) 對于X中的所有的x和y，只要有x R y且x ≠ y，就有，即R是反對稱的。 以偏序集為模型題目中強(qiáng)調(diào)了每個點都有不同的橫縱坐標(biāo)，圖是有向無環(huán)平面圖。求最大流時，可以用樸素的增廣路算法，復(fù)雜度