提高雜項(xiàng)專(zhuān)題強(qiáng)聯(lián)通

1、強(qiáng)連通分支JustForU本講義部分內(nèi)容引用北京大學(xué)信息學(xué)院實(shí)驗(yàn)班袁洋、陳科吉同學(xué)講義，特此致謝強(qiáng)連通分支 在有向圖G中，如果任意兩個(gè)不同的頂點(diǎn)相互可達(dá)，則稱(chēng)該有向圖是強(qiáng)連通的。 有向圖G的極大強(qiáng)連通子圖稱(chēng)為G的強(qiáng)連通分支。計(jì)算強(qiáng)連通分支的兩種方法 Korasaju tarjan 定義DFN(u)為節(jié)點(diǎn)u搜索的次序編號(hào)(時(shí)間戳) Low(u)為u或u的子樹(shù)能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號(hào) Low(u)=Min DFN(u), Low(v),(u,v)為樹(shù)枝邊，u為v的父節(jié)點(diǎn) DFN(v),(u,v)為指向棧中節(jié)點(diǎn)的后向邊(非橫叉邊) 思想： 做一遍DFS，用dfni表示編號(hào)為i的節(jié)點(diǎn)在DFS

2、過(guò)程中的訪(fǎng)問(wèn)序號(hào)(也可以叫做開(kāi)始時(shí)間）用lowi表示i節(jié)點(diǎn)及其下方節(jié)點(diǎn)所能到達(dá)的開(kāi)始時(shí)間最早的節(jié)點(diǎn)的開(kāi)始時(shí)間。初始時(shí)dfni=lowi 在DFS過(guò)程中會(huì)形成一搜索樹(shù)。在搜索樹(shù)上越上層的節(jié)點(diǎn)，顯然dfn的值就越小。 如果發(fā)現(xiàn)某節(jié)點(diǎn)有邊連到搜索樹(shù)中自己的祖先節(jié)點(diǎn)，則更新其low 值。 如果一個(gè)節(jié)點(diǎn)的low 值小于dfn值，那么就說(shuō)明它或其子孫節(jié)點(diǎn)有邊連到自己上方的節(jié)點(diǎn) 如果一個(gè)節(jié)點(diǎn)的low值等于dfn值，則說(shuō)明其下方的節(jié)點(diǎn)不能走到其上方的節(jié)點(diǎn)，那么該節(jié)點(diǎn)u就是一個(gè)強(qiáng)連通分量在DFS搜索樹(shù)中的根。 但是u的子孫節(jié)點(diǎn)未必就和u處于同一個(gè)強(qiáng)連通分量，怎么辦？用棧解決. 從節(jié)點(diǎn)1開(kāi)始DFS，把遍歷到的節(jié)點(diǎn)

3、加入棧中。搜索到節(jié)點(diǎn)u=6時(shí)，DFN6=LOW6，找到了一個(gè)強(qiáng)連通分量。退棧到u=v為止，6為一個(gè)強(qiáng)連通分量。過(guò)程演示 返回節(jié)點(diǎn)5，發(fā)現(xiàn)DFN5=LOW5，退棧后5為一個(gè)強(qiáng)連通分量。過(guò)程演示 返回節(jié)點(diǎn)3，繼續(xù)搜索到節(jié)點(diǎn)4，把4加入堆棧。發(fā)現(xiàn)節(jié)點(diǎn)4向節(jié)點(diǎn)1有后向邊，節(jié)點(diǎn)1還在棧中，所以L(fǎng)OW4=1。節(jié)點(diǎn)6已經(jīng)出棧，(4,6)是橫叉邊，返回3，(3,4)為樹(shù)枝邊，所以L(fǎng)OW3=LOW4=1。過(guò)程演示 繼續(xù)回到節(jié)點(diǎn)1，最后訪(fǎng)問(wèn)節(jié)點(diǎn)2。訪(fǎng)問(wèn)邊(2,4)，4還在棧中，所以L(fǎng)OW2=DFN4=5。返回1后，發(fā)現(xiàn)DFN1=LOW1，把棧中節(jié)點(diǎn)全部取出，組成一個(gè)連通分量1,3,4,2。過(guò)程演示過(guò)程演示 至此，

4、算法結(jié)束。經(jīng)過(guò)該算法，求出了圖中全部的三個(gè)強(qiáng)連通分量1,3,4,2,5,6。void tarjan(int u)dfnu=lowu=+index;s.push(u);instacku=true;for(int e=headu;e!=-1;e=nexte)if(dfnedgee.to=-1)tarjan(edgee.to);lowu=min(lowu,lowedgee.to);else if(instackedgee.to)lowu=min(lowu,dfnedgee.to);if(dfnu=lowu)while(1)int temp=s.top();s.pop();belongtemp=Cou

5、nt;instacktemp=false;if(temp=u)break;Count+; /strongly connect number初始化及運(yùn)行 memset(instack,false,sizeof(instack); memset(dfn,-1,sizeof(dfn); index=0; for(int i=1;i=n;i+)if(dfni=-1)tarjan(i); 無(wú)向連通圖中，如果刪除某點(diǎn)后，圖變成不連通，則稱(chēng)該點(diǎn)為割點(diǎn)。 無(wú)向連通圖中，如果刪除某邊后，圖變成不連通，則稱(chēng)該邊為橋。思路和有向圖求強(qiáng)連通分量類(lèi)似一個(gè)頂點(diǎn)u是割點(diǎn)，當(dāng)且僅當(dāng)滿(mǎn)足(1)或(2)(1) u為樹(shù)根，且u有多

6、于一個(gè)子樹(shù)。(2) u不為樹(shù)根，且滿(mǎn)足存在(u,v)為樹(shù)枝邊(或稱(chēng)父子邊，即u為v在搜索樹(shù)中的父親)，使得DFS(u)=Low(v)。一條無(wú)向邊(u,v)是橋，當(dāng)且僅當(dāng)(u,v)為樹(shù)枝邊，且滿(mǎn)足DFS(u)Low(v)（前提是其沒(méi)有重邊）。上面的 “樹(shù)”指的是在DFS過(guò)程中形成的搜索樹(shù)給定一個(gè)有向圖，求有多少個(gè)頂點(diǎn)是由任何頂點(diǎn)出發(fā)都可達(dá)的。頂點(diǎn)數(shù)= 10,000,邊數(shù) = 50,000有向無(wú)環(huán)圖中唯一出度為0的點(diǎn)，一定可以由任何點(diǎn)出發(fā)均可達(dá)(由于無(wú)環(huán)，所以從任何點(diǎn)出發(fā)往前走，必然終止于一個(gè)出度為0的點(diǎn))1. 求出所有強(qiáng)連通分量2. 每個(gè)強(qiáng)連通分量縮成一點(diǎn)，則形成一個(gè)有向無(wú)環(huán)圖DAG。3. DA

7、G上面如果有唯一的出度為0的點(diǎn),則該點(diǎn)能被所有的點(diǎn)可達(dá)。那么該點(diǎn)所代表的連通分量上的所有的原圖中的點(diǎn)，都能被原圖中的所有點(diǎn)可達(dá)，則該連通分量的點(diǎn)數(shù)，就是答案。4. DAG上面如果有不止一個(gè)出度為0的點(diǎn)，則這些點(diǎn)互相不可達(dá)，原問(wèn)題無(wú)解，答案為0題目大意：N(2N100)各學(xué)校之間有單向的網(wǎng)絡(luò)，每個(gè)學(xué)校得到一套軟件后，可以通過(guò)單向網(wǎng)絡(luò)向周邊的學(xué)校傳輸，問(wèn)題1：初始至少需要向多少個(gè)學(xué)校發(fā)放軟件，使得網(wǎng)絡(luò)內(nèi)所有的學(xué)校最終都能得到軟件。2，至少需要添加幾條傳輸線(xiàn)路(邊)，使任意向一個(gè)學(xué)校發(fā)放軟件后，經(jīng)過(guò)若干次傳送，網(wǎng)絡(luò)內(nèi)所有的學(xué)校最終都能得到軟件。給定一個(gè)有向圖，求：1) 至少要選幾個(gè)頂點(diǎn)，才能做到從這

8、些頂點(diǎn)出發(fā)，可以到達(dá)全部頂點(diǎn)2) 至少要加多少條邊，才能使得從任何一個(gè)頂點(diǎn)出發(fā)，都能到達(dá)全部頂點(diǎn)頂點(diǎn)數(shù)= 100有向無(wú)環(huán)圖中所有入度不為0的點(diǎn)，一定可以由某個(gè)入度為0的點(diǎn)出發(fā)可達(dá)。(由于無(wú)環(huán)，所以從任何入度不為0的點(diǎn)往回走，必然終止于一個(gè)入度為0的點(diǎn))1. 求出所有強(qiáng)連通分量2. 每個(gè)強(qiáng)連通分量縮成一點(diǎn)，則形成一個(gè)有向無(wú)環(huán)圖DAG。3. DAG上面有多少個(gè)入度為0的頂點(diǎn)，問(wèn)題1的答案就是多少在DAG上要加幾條邊，才能使得DAG變成強(qiáng)連通的，問(wèn)題2的答案就是多少加邊的方法：要為每個(gè)入度為0的點(diǎn)添加入邊，為每個(gè)出度為0的點(diǎn)添加出邊假定有 n 個(gè)入度為0的點(diǎn)，m個(gè)出度為0的點(diǎn)，如何加邊？把所有入度為

9、0的點(diǎn)編號(hào) 0,1,2,3,4 .N -1每次為一個(gè)編號(hào)為i的入度0點(diǎn)可達(dá)的出度0點(diǎn)，添加一條出邊，連到編號(hào)為(i+1)%N 的那個(gè)出度0點(diǎn),這需要加n條邊若 m n，則還有m-n個(gè)入度0點(diǎn)，則從這些點(diǎn)以外任取一點(diǎn)，和這些點(diǎn)都連上邊，即可，這還需加m-n條邊。所以，max(m,n)就是第二個(gè)問(wèn)題的解acm1236，acm3180，acm2762（強(qiáng)連通+拓?fù)渑判颍?，acm2553，acm3114（強(qiáng)連通+dijkstra), acm3160(強(qiáng)連通+DP） 對(duì)于點(diǎn)雙連通分支，實(shí)際上在求割點(diǎn)的過(guò)程中就能順便把每個(gè)點(diǎn)雙連通分支求出。建立一個(gè)棧，存儲(chǔ)當(dāng)前雙連通分支，在搜索圖時(shí)，每找到一條樹(shù)枝邊或反向邊，就把這條邊加入棧中。如果遇到某時(shí)滿(mǎn)足DFS(u)=Low(v)，說(shuō)明u是一個(gè)割點(diǎn)，同時(shí)把邊從棧頂一個(gè)個(gè)取出，直到遇到了邊(u,v)，取出的這些邊與其關(guān)聯(lián)的點(diǎn)，組成一個(gè)點(diǎn)雙連通分支。割點(diǎn)可以屬于多個(gè)點(diǎn)雙連通分支，其余點(diǎn)和每條邊只屬于且屬于一個(gè)點(diǎn)雙連通分支。只需在求出所有的橋以后，把橋邊刪除，原圖變成了多個(gè)連通塊，則每個(gè)連通塊就是一個(gè)邊雙連通分支。橋不屬于任何一個(gè)邊雙連通分支，其余的邊和每個(gè)頂點(diǎn)都屬于且只屬于一個(gè)邊雙連通分支。 給你一個(gè)圖，要求你加入最少的邊，使得最后得到的圖為一個(gè)雙連通分支。所謂的雙連通分支，即不存在橋的連通分支。 可以求