ioi2016集訓(xùn)隊(duì)第一次作業(yè)題解

CBAL題目大給定一個(gè)N個(gè)點(diǎn)（從1到N標(biāo)號(hào)）M條邊的有向圖。請(qǐng)你統(tǒng)計(jì)無(wú)序?qū)?XY(XY1X的路徑，和一條從點(diǎn)1到點(diǎn)Y的路徑，且兩條路徑除了點(diǎn)1以外沒(méi)有公共點(diǎn)。1≤n≤0≤m≤數(shù)據(jù)集1（30分）數(shù)據(jù)3（50分）算法分基本概要解決這個(gè)問(wèn)題，先要了解幾對(duì)于一個(gè)有向圖，如果從給定的起點(diǎn)到某個(gè)節(jié)點(diǎn)X的所有路徑都經(jīng)過(guò)節(jié)點(diǎn)X的必經(jīng)點(diǎn)中離起點(diǎn)最遠(yuǎn)（X最近）X的最近必經(jīng)點(diǎn)（immediatedominator），記idom[X]=Y。最近必經(jīng)點(diǎn)是唯一的。將除起點(diǎn)外所有節(jié)點(diǎn)與最近必經(jīng)點(diǎn)連接構(gòu)成一棵樹(shù)，稱為支配樹(shù)（DominatorTree。相乘并累加即是滿足條件的無(wú)序?qū)€(gè)數(shù)。因此本題的重點(diǎn)在于如何快速求出給定有向圖的支配樹(shù)。DAGG上的節(jié)點(diǎn)有嚴(yán)格的拓?fù)湫?，即只能從一個(gè)拓?fù)湫蚩壳暗狞c(diǎn)到達(dá)一個(gè)拓?fù)湫蚩亢蟮狞c(diǎn)。在這種情況下，某個(gè)節(jié)點(diǎn)的最近必經(jīng)點(diǎn)一定是拓?fù)湫蚋〉狞c(diǎn)，我們可以按照拓?fù)湫蛟隽繕?gòu)造支配樹(shù)。1～X1的節(jié)點(diǎn)組成的支配樹(shù)，現(xiàn)在要加入節(jié)XX的節(jié)點(diǎn)，這些節(jié)點(diǎn)的最近公共祖先（LCA）就是節(jié)點(diǎn)X的最近必經(jīng)點(diǎn)，據(jù)此將節(jié)點(diǎn)X加入支配樹(shù)中。LCAO((NMlogN)30NMDFS，如果能到達(dá)某個(gè)節(jié)點(diǎn)，則被刪除的點(diǎn)不是這個(gè)節(jié)點(diǎn)的必經(jīng)點(diǎn)。忽略所有不可達(dá)點(diǎn)，時(shí)間復(fù)雜度O(NM)，能得到20分。結(jié)合DAG上的算法可以得到50分?？焖偎銓?duì)于NM比較大的圖，可以使用Lengauer-Tarjan算法計(jì)算Lengauer-Tarjan算法分為以下三個(gè)DFSDFS對(duì)于一個(gè)節(jié)點(diǎn)Y，存在祖先X能通過(guò)一系列節(jié)點(diǎn)pi（可以為0個(gè)）到達(dá)節(jié)點(diǎn)Y，且?i,dfi>dfn[Y]，稱節(jié)點(diǎn)X是節(jié)點(diǎn)Y的半必經(jīng)點(diǎn)（semidominator），記semi[YX半必經(jīng)點(diǎn)可以通過(guò)半必經(jīng)點(diǎn)定理計(jì)算。半必經(jīng)點(diǎn)定理描述對(duì)于一個(gè)節(jié)點(diǎn)Y，考慮所有能直接到達(dá)它的節(jié)點(diǎn)，設(shè)其中一個(gè)為dfn[Xdfn[Y]，此XZ，滿dfn[Z>dfn[Y時(shí)，semi[Z]為可能的半必經(jīng)點(diǎn)以上所有可能的節(jié)點(diǎn)中，DFS時(shí)間戳（dfn）最小的節(jié)點(diǎn)為Y的半必經(jīng)半必經(jīng)點(diǎn)不一定是必經(jīng)點(diǎn)，需要通過(guò)必經(jīng)點(diǎn)定理修正。必經(jīng)點(diǎn)定理描Xsemi[X的路徑上的其它節(jié)點(diǎn)，記其中半必經(jīng)點(diǎn)時(shí)間戳最小的節(jié)點(diǎn)為Z；semi[Z]=semi[X]idom[X]=semi[Z?=semi[X]idom[Xidom[Z]實(shí)注意到，在計(jì)算半必經(jīng)點(diǎn)的過(guò)程中如果某個(gè)節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的時(shí)間戳比它大，需要這個(gè)前驅(qū)結(jié)點(diǎn)的所有時(shí)間戳比當(dāng)前考慮節(jié)點(diǎn)大的祖先。計(jì)算最近必經(jīng)點(diǎn)的過(guò)程中也要考慮它和半必經(jīng)點(diǎn)之間的路徑上的所有節(jié)點(diǎn)?？梢园凑諘r(shí)間戳逆序計(jì)算每個(gè)節(jié)點(diǎn)的半必經(jīng)點(diǎn)，此時(shí)所有時(shí)間戳更小的節(jié)點(diǎn)仍未計(jì)算，在考察時(shí)間戳大的祖先時(shí)可以直接它在已計(jì)算節(jié)點(diǎn)森林中的所有祖先。已計(jì)算節(jié)點(diǎn)森林可以用并查集來(lái)實(shí)現(xiàn)。在計(jì)算最近必經(jīng)點(diǎn)時(shí)，在某個(gè)節(jié)點(diǎn)剛被加入已計(jì)算節(jié)點(diǎn)森林時(shí)立即計(jì)算以它為半必經(jīng)點(diǎn)的所有節(jié)點(diǎn)的最近必經(jīng)點(diǎn)。O((NMlogN)1O(NM)，能得到本題所有算法相關(guān)Lengauer-Tarjan算法正確性的嚴(yán)謹(jǐn)證明，可見(jiàn)于“AFastForFindingDominatorsina1本題中并查集具有祖先關(guān)系，不能按秩合并。根據(jù)“Worst-CaseysisofSetUnionAlgo