Traffic解題報(bào) 給定一個(gè)n個(gè)節(jié)點(diǎn)的無(wú)向圖，圖中最開(kāi)始沒(méi)有一條邊，所有的點(diǎn)都是孤點(diǎn)。你要依次處理m條命令，分為三種：分別是增加一條邊、刪除一條邊、以及詢n≤100，總操作數(shù)m≤40000這事實(shí)上是一道很經(jīng)典的問(wèn)題了，就是任意圖的連通性問(wèn)題。利用實(shí)上是和m同級(jí)的，也就是說(shuō)，判斷兩個(gè)點(diǎn)是不是在同通分量，不作任何預(yù)處理的的情況下是O(m)的。這樣總時(shí)間復(fù)雜度就高達(dá)O(m2)，顯然是生成樹(shù)：由圖中的邊和點(diǎn)組成的樹(shù)，稱之為生成樹(shù)生成森林：由生成樹(shù)組成集合，它包含所有原圖中的點(diǎn)的。最大生成森林a、b，它們?cè)谏缮种刑幱谕活w樹(shù)，當(dāng)且僅當(dāng)它們?cè)谠瓐D中處于同通分量。那么如果程序能夠在每次詢問(wèn)之前，都保證一個(gè)當(dāng)前圖的最大生成森林，則判斷兩個(gè)點(diǎn)是不是在同通分量就最多只需要O(n)的時(shí)間復(fù)雜度了，因?yàn)樯缮种械倪叺臄?shù)目肯定不會(huì)超過(guò)n。成森林的性質(zhì)。這并不復(fù)雜，時(shí)間復(fù)雜度不超過(guò)O(n)。新合并成一棵樹(shù)，這一步的時(shí)間復(fù)雜度高達(dá)O(m)。操作的時(shí)間復(fù)雜度達(dá)到了O(m)。不妨冷靜的思考這是為什么呢？其實(shí)這里的整體搜索很大程度上是因?yàn)樵谶叺臅r(shí)候盲目的舍棄某條可能的有用不是就有可能需要當(dāng)初舍棄了的邊呢？真正需要改進(jìn)的其實(shí)是的對(duì)于一條圖中無(wú)向邊e，設(shè)D(e)表示e這條邊被刪除的時(shí)間（也可先把這條邊，并把這條邊之后和與這顆樹(shù)上的其他邊形成的圈找出來(lái)作序列中被刪除的環(huán)上作序列中被刪除的環(huán)上在圖中假設(shè)是紅色的邊然后將圈中的邊中D值最小的邊，也就是最早將在操作序列中被刪去的邊，新的邊D值最小，就相當(dāng)于沒(méi)有。這樣做的時(shí)間復(fù)雜度還是O(n)，因定義，可以知道D((c,d))>D((a,b))。可以知道(c,d)必然是因?yàn)槟硹l其他邊的緣故而被刪除出生成森林的，如果這條邊是(a,b)則已經(jīng)。因?yàn)槊看问莿h除DD((a,b))<D((c,d))，(a,b)不可能促使(c,d)被刪除。所以必然被刪除，所以D((e,f))>D((c,d))>D((a,b))。(e,f)和(a,b)成圈，所以必然已經(jīng)被刪除……如此反復(fù)推倒，因?yàn)檫叺臄?shù)量有限，所以最后必然會(huì)推倒出某條邊(x,y)是因?yàn)?a,b)被刪除的，但卻D((x,y))>D((a,b))，則！這樣整個(gè)算法的框架就出來(lái)了，D數(shù)組可以先一遍預(yù)處理O(m)全部求出來(lái)，每次詢問(wèn)操作是O(n)