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