算法 {Tarjan算法,强连通分量SCC,BCC双连通分量,割点,割边/桥}

算法 {Tarjan算法,强连通分量SCC,BCC双连通分量,割点,割边/桥}

算法 {Tarjan算法,强连通分量SCC,BCC双连通分量,割点,割边/桥}
@LOC: 3

有向图-SCC強聯通分量

定義

#SCC強聯通分量Strongly Connected Component#
有向圖G的所有點 劃分為若干個不相交的子集S1,S2,..., Si對應的導出子圖是強聯通的;
G的所有邊 分為2類: {1:[在Si的導出子圖裡]; 2:[形如Si->Sj]};

相關定義

#連通子圖#
有向圖G, 對於其子圖SG 如果他是連通的(這裡的連通 是泛型的 你可以定義為{強/半/弱})(即此時單獨考慮SG 與G無關) 則SG為G的連通子圖;

#連通分量CCConnected Component(連通塊)#
極大的連通子圖(這裡的連通 是泛型的 你可以定義為{強/半/弱}) 為連通分量; 有向圖G的所有連通子圖 在包含關係下為偏序關係, 其所有極大元 為G的所有連通分量;
連通分量 一定是導出子圖, 因為對於連通分量CC 增加其內部的邊 不會影響CC的連通性; 因此 連通分量可以直接用(點集)來表示;

舉例
G: (a->b->c) (d->e), a->b為連通子圖, a->b->c是連通分量(當然也是連通子圖);

@DELI;

#強聯通SCStrongly Connceted#
對於有向圖G, 任意兩個點a,b是強連通的 ⟺ iff ⟺ (a可達b) 且 (b也可達a);

@DELI;

#有向圖是強連通的#
有向圖G, 如果(G的任意兩個點 都是強連通的) ⟹ implies ⟹ G是強連通的;

@DELI;

#有向圖中兩點間的連通性#
對於有向圖G, 任意兩個點a,b是連通的 ⟺ iff ⟺ (a可達b) 或 (b可達a);

@DELI;

#SCC的縮點#
令有向圖DAG滿足: 原圖G中的任意邊a->b, 如果Scc_id[a] != Scc_id[b], 則他對應在圖DAG中為Scc_id[a] -> Scc_id[b]的一條有向邊;
即 可以想象為: 原圖G中的一個SCC(他由很多點組成) 縮成了一個DAG中的一個點;

性質

@DELI;

對於一個強聯通的有向圖G, G裡面的兩個點a,b 其滿足: 刪除原圖G中的任何一條有向邊後 a,b仍然是連通的(只不過 可能不是強連通了, 比如原來是a可達b && b可達a 而現在變成了a可達b 但b不可達a);

算法

模板代碼

namespace ___Tarjan_SCC{
vector<int> SCC_id;   // `SCC_id[a]=b`: 圖中的`a`點所在的SCC(強聯通塊)的ID號為`b`(滿足`0<=b<SCC_count`);
vector<int> SCC_size; // `SCC_size[a]=b`: ID號為`a`的SCC 他由`b`個點組成; `SCC_size.size()`為SCC的個數;
stack<int> __Stk;
vector<int> __DfsId, __LowId;
int __DfsIdCounter;
const ___Graph * __DiG; // 要處理的*有向圖*;void __Dfs( int _cur){__Stk.push(_cur);  __DfsId[ _cur] = __DfsIdCounter ++;  __LowId[_cur] = __DfsId[_cur];for( int nex, edge = __DiG->Head[ _cur]; ~edge; edge = __DiG->Next[ edge]){nex = __DiG->Vertex[ edge];if( -1 == __DfsId[ nex]){ __Dfs( nex);}if( -1 == SCC_id[ nex]){ MinSelf_( __LowId[ _cur], __LowId[ nex]);}}if( __DfsId[ _cur] == __LowId[ _cur]){SCC_size.push_back( 0);while( true){int temp = __p();  __Stk.pop();SCC_id[ temp] = SCC_size.size() - 1;  SCC_size.back() ++;if( temp == _cur){ break;}}}
}
void Work( const ___Graph & _DiG){__DiG = &_DiG;size( __DiG->PointsCount);  memset( SCC_id.data(), -1, sizeof( SCC_id[0]) * SCC_id.size());  SCC_size.clear();while( false == __pty()){ __Stk.pop();}__size( __DiG->PointsCount);  __size( __DiG->PointsCount);  memset( __DfsId.data(), -1, sizeof( __DfsId[0]) * __DfsId.size());__DfsIdCounter = 0;for( int i = 0; i < __DiG->PointsCount; ++i){if( -1 == __DfsId[ i]){ __Dfs( i);}}
}
void Build_DAG( ___Graph & _dag){
//< *SCC的縮點*;_dag.Initialize( SCC_size.size());for( int cur = 0; cur < __DiG->PointsCount; ++cur){for( int nex, edge = __DiG->Head[cur]; ~edge; edge = __DiG->Next[edge]){nex = __DiG->Vertex[ edge];if( SCC_id[ cur] == SCC_id[ nex]){ continue;}_dag.Add_edge( SCC_id[ cur], SCC_id[ nex], __DiG->Weight[ edge]);}}
}
} // namespace ___Tarjan_SCC

注釋

SCC算法 依靠的核心是: 一個SCC(點集) 在DFS樹中 是一個子樹(這裡不是說的以x為根的子樹, 而是子樹 他的定義是子樹是一個點集S, S中任何兩點 在原樹中的路徑上的所有點 都在S中), 因為子樹 一定只有1個(樹根) 也就是最小時間戳; 即當DFS回溯到這個(子樹的樹根)時 此時stack裡頂層的連續一段存儲的 就是這個子樹 即這個割集 即stack形如[, SCC];

@DELI;

LowId是Tarjan算法的核心;
他的定義: 對於一個SCC 令其最小的DfsId[st]為mi, 則我們的目的是 對任意 x ∈ S C C x in SCC x∈SCC
. 1(x==st):[LowId[st]=mi];
. 2(x!=st):[LowId[x] != DfsId[t], 且t in SCC, DfsId[t] < DfsId[x]]; 換句話說, 此時x的LowId值 等於該SCC內某個點t的時間戳 且滿足t的時間戳是小於DfsId[x]的;
也就是, 只要不是在st這個點 那麼他的LowId一定不等於他的DfsId (即這個點 仍然會留在stack裡面), 只有當在st這個點時 才會有LowId = DfsId (然後此時stack=[... st, others]);
比如0<->1<->2 (先遍歷1->2然後才是1->0), 最終會得到Low[0,1] = 0, Low[2]=1;
. 因此 代碼中的MinSelf_( __LowId[ _cur], __LowId[ nex]); 你寫成DfsId[nex]也可以, 你寫成LowId[nex] 並不能保證 一個SCC裡的所有點的LowId值都相同, 比如上面這個樣例;

@DELI;

對於當前的Dfs(cur)中的一條邊cur->nex 有如下幾種情況:

for( int nex, edge = __DiG->Head[ _cur]; ~edge; edge = __DiG->Next[ edge]){nex = __DiG->Vertex[ edge];if( -1 == __DfsId[ nex]){ __Dfs( nex);if( SCC_id[nex] != -1): *第1類邊*;else: *第2類邊*;}else{if( `nex,cur`不是同一個*DFS樹*上): *第3類邊*;elif( `SCC_id[nex] != -1`): *第4類邊*;else: *第5類邊*;}
}`SCC_id[x]!=-1`等價於`IsInStk[x]=false`;

1(DfsId[nex] == -1): 即此時要進行Dfs(nex), 即這條邊是DFS樹上邊, 此時分2種情況:
. 第1類邊; @IF(SCC_id[nex] != -1)):[ cur,nex不在同一個SCC裡, 當前邊是橫跨2個SCC的];
. 第2類邊;@ELSE:[cur,nex在同一個SCC裡, 此時要執行MinSelf( LowId[cur], LowId[nex]); 比如0->1->2->0, Dfs(2)之後此時Low[2]=0 回溯到Dfs(1)時 更新Low[1]=0;];
2(DfsId[nex] != -1): 此時 即Dfs(nex)先前已經調用過了 此時分為3種情況:
. 第3類邊;@IF(nex不是當前DFS樹裡的節點):[ 比如0, 1->0 第一次的DFS樹是0 第二次的DFS樹是1, 此時訪問到(先前的DFS樹)上的節點 而先前的DFS樹 他的SCC都已經確定了; 因此 cur,nex不在同一個SCC裡, 當前邊是橫跨2個SCC的];
. 第4類邊; @ELIF(SCC_id[nex]!=-1):[ nex是當前DFS樹的節點 但是他所在的SCC已經確定; 比如0->1, 0->2->1 對於Dfs(2)時的2->1這條邊 此時1所在的SCC{1}已經確定; 跟上面@IF的情況一樣 cur|nex不會在同一個SCC裡];
. 第5類邊; @ELSE:[SCC_id[nex]==-1):[ nex是當前DFS樹的節點 且此時nex是DFS樹上的cur的祖先節點, 即存在一條nex->...->cur的路徑(也就是當前的DFS棧是形如[...nex,...,cur]) 然後當前又出現了一條cur->nex的路徑, 此時形成了一個環,因此cur,nex這個環 一定是強聯通的 因此更新MinSelf( LowId[cur], LowId[nex]);]

性質

例题

@LINK: ;

筆記

For a (directed) graph G = ( V , E ) G = (V,E) G=(V,E), let I d [ v ] Id[v] Id[v] is the SCC-ID of v ∈ V v in V v∈V which within the range [0, SCC-Count).

A DFS-Order-Sequence of a graph is [ 0 , 1 , 2 , . . . , n ) [0, 1, 2, ..., n) [0,1,2,...,n), we use O r d e r [ v ] Order[v] Order[v] represents its DFS-Order.

Let L o w [ v ] Low[v] Low[v] denotes a DFS-Order such that L o w [ v ] = O r d e r [ w ] Low[v] = Order[w] Low[v]=Order[w] such that O r d e r [ w ] ≤ O r d e r [ v ] Order[w] leq Order[v] Order[w]≤Order[v] and w , v w,v w,v are in the same SCC
. If there exists a point w w w such that O r d e r [ w ] < O r d e r [ v ] Order[w] < Order[v] Order[w]<Order[v] and w , v w,v w,v in the same SCC, then L o w [ v ] < O r d e r [ v ] Low[v] < Order[v] Low[v]<Order[v]; otherwise L o w [ v ] = O r d e r [ v ] Low[v] = Order[v] Low[v]=Order[v] if and only if O r d e r [ v ] Order[v] Order[v] is the minimal-Order in its SCC (every SCC has exactly one such point, we call such a point The Root of SCC).

+ e.g., G = ( 1 → 2 ) ( 2 → 3 ) ( 3 → 4 ) ( 4 → 3 ) ( 2 → 5 ) ( 5 → 2 ) ( 2 → 1 ) G = (1to 2)(2to 3)(3to 4)(4to 3)(2to 5)(5to 2)(2to 1) G=(1→2)(2→3)(3→4)(4→3)(2→5)(5→2)(2→1) (note the order of edges is also the process of DFS(1)), then we have 2 2 2 SCC ( 1 , 2 , 5 ) ( 3 , 4 ) (1,2,5) (3,4) (1,2,5)(3,4); finally, L o w [ 1 ] = 0 , L o w [ 2 ] = 0 , L o w [ 5 ] = 1 Low[1] = 0, Low[2] = 0, Low[5]=1 Low[1]=0,Low[2]=0,Low[5]=1, all L o w [ v ] Low[v] Low[v] in a SCC maybe not the same; L o w [ 2 ] = 0 Low[2] = 0 Low[2]=0 cuz there is O r d e r [ 1 ] = 0 < O r d e r [ 2 ] = 1 Order[1] = 0 < Order[2]=1 Order[1]=0<Order[2]=1; L o w [ 5 ] = 1 Low[5] = 1 Low[5]=1 cuz there is O r d e r [ 2 ] = 1 < O r d e r [ 5 ] = 4 Order[2] = 1 < Order[5]=4 Order[2]=1<Order[5]=4 ( L o w [ 5 ] Low[5] Low[5] can also equals O r d e r [ 1 ] = 0 Order[1] = 0 Order[1]=0); 0 0 0 is the root of the SCC 1 , 2 , 5 1,2,5 1,2,5)

---

When we at D f s ( c u r ) Dfs( cur) Dfs(cur) and iterating its adjacent-points n e x nex nex, there are several steps:
+ Firstly, we set Order[cur] = Low[cur] = DFS_order ++ (cuz Low[cur] <= Order[cur] finally, so we set it equals to Order[cur] initially)
+ If nex has never been called by DFS, so we call D f s ( n e x ) Dfs(nex) Dfs(nex); and then we update L o w [ c u r ] = m i n ( s e l f , L o w [ n e x ] ) Low[cur] = min(self, Low[nex]) Low[cur]=min(self,Low[nex]) (cuz nex never be DFS visited, if c u r , n e x cur, nex cur,nex is not in the same SCC and O r d e r [ n e x ] > O r d e r [ c u r ] Order[nex] > Order[cur] Order[nex]>Order[cur], we have n e x nex nex must the Root of its SCC, so L o w [ n e x ] > O r d e r [ c u r ] Low[nex] > Order[cur] Low[nex]>Order[cur]; this operation is ineffective), otherwise c u r , n e x cur,nex cur,nex in the same SCC, if c u r cur cur is the Root then L o w [ n e x ] = O r d e r [ c u r ] Low[nex] = Order[cur] Low[nex]=Order[cur], so this operations is also ineffective; if c u r cur cur is not the Root, there must exists a point n e x 1 nex1 nex1 whose L o w [ n e x 1 ] < O r d e r [ c u r ] Low[nex1] < Order[cur] Low[nex1]<Order[cur] (cuz there must has a path c u r → n e x 1 → . . → r o o t cur to nex1 to .. to root cur→nex1→..→root where . . . ... ... do not contains c u r cur cur, therefore L o w [ n e x 1 ] = O r d e r [ r o o t ] < O r d e r [ c u r ] Low[nex1] = Order[root] < Order[cur] Low[nex1]=Order[root]<Order[cur]);

+ When DFS returns to a root-point Low[] = Order[], then the DFS-Stack must be in the form [...., root, S] where any point that in the same SCC with root, must occurs in S;

Code

void dfs( int _cur){queue[ tail ++] = _cur;isInQueue[ _cur] = true;dfsOrderId[ _cur] = dfsOrderId_counter ++;lowest_orderId[ _cur] = dfsOrderId[ _cur];//--for( int nex, i = graph->Head[ _cur]; ~i; i = graph->Next[ i]){nex = graph->Vertex[ i];if( -1 == dfsOrderId[ nex]){ //< never `dfs( nex)` calleddfs( nex);}if( isInQueue[ nex]){ //< `nex` maybe already forms a SCC, we should aviod this case; e.g., (1<->2)<-3, so Low[2] cann't be used to updated Low[3]lowest_orderId[ _cur] = min( lowest_orderId[ nex], lowest_orderId[ _cur]);}}if( lowest_orderId[ _cur] == dfsOrderId[ _cur]){scc_size[ scc_id_counter] = 0;while( true){int c = queue[ tail - 1];isInQueue[ c] = false;-- tail;scc_id[ c] = scc_id_counter;++ scc_size[ scc_id_counter];if( c == _cur){ break;}}++ scc_id_counter;}
}

Actually, the array dfsOrderId, lowest_orderId can be omitted; (use scc_id to denote lowest_orderId, cuz when DFS not yet returned to root, the array scc_id is free; and once a SCC is fixed (i.e., DFS has returned to its root, any other points (not belongs to this SCC) would not visit/use any information of this SCC)

 void dfs( int _cur){ptrNew_queue[ queue_tail ++] = _cur;ptrNew_isInQueue[ _cur] = true;int current_dfsOrderId = dfsOrderId_counter;ptrNew_sccId[ _cur] = dfsOrderId_counter ++;//--for( int nex, i = ptrRef_graph->Head[ _cur]; ~i; i = ptrRef_graph->Next[ i]){nex = ptrRef_graph->Vertex[ i];if( -1 == ptrNew_sccId[ nex]){ //< never `dfs( nex)` calleddfs( nex);}if( ptrNew_isInQueue[ nex]){ptrNew_sccId[ _cur] = min( ptrNew_sccId[ nex], ptrNew_sccId[ _cur]);}}if( ptrNew_sccId[ _cur] == current_dfsOrderId){ptrNew_sccSize[ scc_id_counter] = 0;while( true){int c = ptrNew_queue[ queue_tail - 1];ptrNew_isInQueue[ c] = false;-- queue_tail;ptrNew_sccId[ c] = scc_id_counter;++ ptrNew_sccSize[ scc_id_counter];if( c == _cur){ break;}}++ scc_id_counter;}
}

无向图-BCC雙連通分量(桥)

定義

#BCC雙聯通分量Bi-Connected Component#
無向圖G的所有點 劃分為若干個不相交的子集S1,S2,..., Si對應的導出子圖是雙聯通的;
G的所有邊 分為2類: {1:[在Si的導出子圖裡]; 2:[形如Si-Sj]};

相關定義

#BCC的縮點#
令無向樹Tree滿足: 原圖G中的任意邊a-b, 如果BCC_id[a] != BCC_id[b], 則他對應在圖Tree中為BCC_id[a] -> BCC_id[b]的一條無向邊;
即 可以想象為: 原圖G中的一個BCC(他由很多點組成) 縮成了Tree中的一個點;

@DELI;

#BC雙連通Bi-Connected#
對於無向圖G, 任意兩點a,b 如果(存在兩條路徑P1: a-...-b, P2: a-...-b, 對於P1裡的任何一條線 都不會出現在P2裡) ⟹ implies ⟹ a,b是雙連通的;

@DELI;

#割邊#
無向圖G中的某條無向邊E 為割邊 ⟺ iff ⟺ 存在兩個點a,b 他倆在G中是連通的 但是去除掉E后 他倆是不連通的 ⟺ iff ⟺ G的CC個數為X 但是去掉E後 圖的CC個數為X+1;

@DELI;

#雙連通的無向圖#
無向圖G是雙連通的 ⟺ iff ⟺ (G的任意兩個點 都是雙連通的) ⟺ iff ⟺ G不存在割邊;

@DELI;

#無向圖中兩點間的連通性#
無向圖中的兩點a,b 如果存在一條路徑<-b 則稱a,b是連通的;

@DELI;

性質

對於一個(雙連通的無向圖G), 因為不存在割邊 所以你刪除任意一條無向邊後 這個圖滿足(任意兩個點是連通的 但不再是雙連通);

@DELI;

縮點之後得到的樹, 他一定是不含有重複邊的, 這一點 與SCC是不同的(SCC的縮點後 他的DAG裡 是可能有重複邊);
這是因為 你縮點後得到的樹 他的邊 就對應原圖的割邊, 假如有重複邊 他就不是割邊了;

算法

模板代碼

namespace ___Tarjan_BCC{
vector<int> BCC_id; // `BCC_id[a]=b`: 圖中的`a`點所在的BCC(雙聯通塊)的ID號為`b`(滿足`0<=b<BCC_size.size()`);
//< 對於一條無向邊`a-b` 如果`BCC_id[a] != BCC_id[b]` 則說明這條邊為*割邊(橋)*;
vector<int> BCC_size; // `BCC_size[a]=b`: ID號為`a`的EBCC 他由`b>0`個點組成; `BCC_size.size()`表示總共BCC的個數;
stack<int> __Stk;
vector<int> __DfsId, __LowId;
int __DfsIdCounter;
const ___Graph * __UnDiG; // 必須為*無向圖*, 即邊的ID`e,e^1`是一對有向邊(一正一反)void __Dfs( int _cur, int _faEdge){__Stk.push( _cur);  __LowId[ _cur] = __DfsId[ _cur] = __DfsIdCounter ++;for( int nex, edge = __UnDiG->Head[ _cur]; ~edge; edge = __UnDiG->Next[ edge]){if( (edge^1) == _faEdge){ continue;}nex = __UnDiG->Vertex[ edge];if( -1 == __DfsId[ nex]){ __Dfs( nex, edge);//>< [`LowId[nex]==DfsId[nex]`]->[當前邊`cur-nex`為橋]}MinSelf_( __LowId[ _cur], __LowId[ nex]);}if( __LowId[ _cur] == __DfsId[ _cur]){BCC_size.push_back( 0);while( true){int temp = __p();  __Stk.pop();  BCC_id[ temp] = BCC_size.size() - 1;  BCC_size.back() ++;  if( temp == _cur){ break;}}}
}
void Work( const ___Graph & _graph){ASSERT_MSG_( "`_graph`必須為*無向圖*, 即邊的ID`e,e^1`是一對有向邊(一正一反)");__UnDiG = &_graph;size( _graph.PointsCount);  BCC_size.clear();while( false == __pty()){ __Stk.pop();}  __size( _graph.PointsCount);  __size( _graph.PointsCount);memset( __DfsId.data(), -1, sizeof( __DfsId[0]) * __DfsId.size());  __DfsIdCounter = 0;for( int i = 0; i < _graph.PointsCount; ++i){if( -1 == __DfsId[ i]){ __Dfs( i, -1);}}
}
void Build_tree( ___Graph & _tree){
//< BCC的縮點;_tree.Initialize( BCC_size.size());for( int ea, eb, b, a = 0; a < __UnDiG->PointsCount; ++a){for( int __edge = __UnDiG->Head[ a]; ~__edge; __edge = __UnDiG->Next[ __edge]){b = __UnDiG->Vertex[ __edge];ea = BCC_id[ a], eb = BCC_id[ b];if( ea != eb){_tree.Add_edge( ea, eb, __UnDiG->Weight[ __edge]);}}}
}
} // namespace ___Tarjan_BCC

注釋

連通無向圖G, a為G的某點, 令DG為以a為起點的DFS圖, 即 此時得到了一個(G的無向邊<->DG的有向邊)之間的雙射;
性質:[DG的SCC 對應於 G的BCC];
因此 無向圖的BCC算法 本質上 就是有向圖的SCC算法, 直接代碼複製過來就可以;

@DELI;

MinSelf_( __LowId[ _cur], __LowId[ nex]);這個代碼 是和SCC不同的 (這是優化, 即你可以讓他和SCC的代碼完全一樣 這是正確的), 在SCC裡 他有一個if( SCC_id[nex] == -1)的判斷 但在BCC裡 不需要這個判斷;
. 因為 當SCC_id[nex] != -1時, 此時有2種情況: {1(nex與cur不是在同一個DFS樹上):[這種情況在無向圖的DFS樹上不會存在, 因為一個連通無向圖只會有一個DFS樹(不管起點是誰) 不會是DFS樹的森林]; 2(nex其SCC已經確定了):[這種情況 在無向圖中也不會發生, 因為當前邊cur-nex 假如nex的SCC已經確定 那麼在DFS圖中 他會對應的是nex->cur, 即當前的cur->nex不會出現在DFS樹中]};
因此 作為優化, 這個判斷 可以去掉 (不用對SCC_id進行memset(-1)操作);

性質

對於一個橋a-b (假如DfsId[a] < DfsId[b]), 令B為b所在的BCC, 則b為B的最小時間戳;
. 因為原圖一定形如?1-a-b-?2 b所有能達到的點 要麼是a 要麼是?2, 而所有的?2的時間戳 都是小於b的;
. 此時b,?2在DFS樹中 一定都是a的子節點; 換句話說, a->b是DFS樹上的邊, 且b,?2這些點 對應為DFS樹中的一個以b點為樹根的子樹;

去除一個橋後 剩餘2個連通塊的大小

定義

對一個連通圖G中的一個橋a-b, 將這條邊刪除後 原圖會分裂為2個連通圖A,B, 求|A|, |B|的大小;

性質

對於一個橋a-b (假如DfsId[a] < DfsId[b]), 令B為b所在的BCC, 則b為B的最小時間戳;
. 因為原圖一定形如?1-a-b-?2 b所有能達到的點 要麼是a 要麼是?2, 而所有的?2的時間戳 都是小於b的;
. 此時b,?2在DFS樹中 一定都是a的子節點; 換句話說, a->b是DFS樹上的邊, 且b,?2這些點 對應為DFS樹中的一個以b點為樹根的子樹, 因此令TreeSum[x]為DFS樹中以x為樹根的子樹大小, 那麼TreeSum[b]就等於b,?2這些點;

代碼模板

*`TreeSum[ G.PointsCount] = {0}`*void Dfs_( _cur){*TreeSum[_cur] = 1;*for( nex : cur鄰接點){if( -1 == __DfsId[ nex]){__Dfs( nex, edge);*TreeSum[ _cur] += TreeSum[ nex];*//>< [`LowId[nex]==DfsId[nex]`]->[當前邊`cur-nex`為橋]if( __LowId[nex]==__DfsId[nex]){`TreeSum[nex] 與 G.PointsCount-TreeSum[nex]`為答案;}}}
}

例题

@LINK: /
對一個連通的無向圖 進行EBCC縮點後 得到一個無向無根樹T(不是森林), 求最少添加幾條邊 可以使得這個T 變成是雙聯通的;
. 令T的葉子節點有x個, 則答案為(x+1)/2; (比如葉子是{a,b,c} 則連接a-b, c-a); 注意 這裡的葉子 (不可以是根節點), 即如果T只有1個點 那麼他的葉子節點為0個 而不是1個! (因為如果T只有1個點 那麼T本身就是雙連通的 不需要添加變, 即原圖G 本身就是雙連通的 那麼他對應的T 就是只有1個點 此時不需要加邊);

    int leaf = 0;{FOR_( i, 0, Tree.PointsCount-1){int c = 0;for( int e = Tree.Head[i]; ~e; e = Tree.Next[e]){++ c;}if( c == 1){ ++ leaf;} // 不是`c <= 1`;}}cout<< (leaf+ 1) / 2<< ED_;

筆記

Some properties of the algorithm:
+ for a connected-graph G G G, let E E E be the edges of its DFS-Tree, then all E P C C EPCC EPCC are the S C C SCC SCC of G − E G - E G−E; therefore perform the SCC-Algorithm on the graph G − E G - E G−E; (understand the nature of SCC algorithm is very vital, E B C C , P B C C EBCC, PBCC EBCC,PBCC are both based on it)
+ cuz all edges are undirected, for a edge ( c u r − n e x ) (cur-nex) (cur−nex), n e x nex nex must be in the Stack if n e x nex nex has been visited by DFS, so the array On_stack can be removed.

割點

定義

#割點#
無向圖G的某點x, 對於三點{a,b,x}互不相同 且a,b是連通的, 但如果將x點(以及其臨界邊)去掉後 a,b是不連通的, 則x為割點;

@DELI;

#余割集#
將無向圖G的所有割點去掉後 剩餘的每個連通塊(也是導出子圖), 為餘割集(點集);
. 比如{1-2-3, 4-5}的餘割集為:{1,3,4-5};

#余割集的鄰接點#
一個余割集S的鄰接點x為: [ x ∉ S xnotin S x∈/S]&&[原圖中存在一條x-S的邊];
. 鄰接點一定是割點;

@DELI;

#割集CutSet#
割集為: 餘割集 + 其鄰接點;
. 比如{1-2-3}的割集為{1-2, 2-3};

相关定义

#餘割集的縮點#
對餘割集進行縮點 割點不動;
. 比如0-1-2-0, 3-4-5-3, 2-5-6-7-2, 此時割點是2,5 有3個餘割集A(0,1) B(3,4) C(6,7), 縮點後 變成A-2-5-B, 2-C-5;

性質

@MARK: @LOC_1;
@IF: 對於DFS樹的根節點(即DFS的起始節點), 他的DFS樹的子節點個數 就等於他的割集個數(包含該點的割集個數, 對應於代碼中的cc_count);
. 根節點R在DFS樹的子節點有a,b,c (即你刪除這個節點後 圖會分裂成3個連通塊), 但是並不意味著 這個點在原圖中有3個鄰接點, 他在原圖的鄰接點可以是{a,aa,b,bb,c,cc} 只不過a,aa是連通的 即你DFS(a)裡面 會訪問到aa 因此aa不會是R的DFS樹裡的子節點 雖然在原圖中aa是RR的鄰接點;
@ELSE: 而一個非根節點X 令他的父節點為fa 令他在DFS樹中的子節點為{a,b,c}, 則X的割集個數(即cc_count) 要麼等於4 要麼等於3; 首先 a,b,c都是割集 (即去掉X後 他們肯定是不連通的 否則如果b,c和a是連通的 那麼DFS(a)會訪問到b,c 也就是 b,c不會是X的DFS樹中的子節點), 因此cc_count >= 3, 但是這個a 他可能與fa是連通的, 即DFS(a)會訪問到fa, 也可能不連通, 即去掉X後 要麼是{ (fa,a), b, c} 要麼是{fa, a, b, c};
. 當然 雖然從DFS樹角度 X的鄰接點是{fa,a,b,c}, 但原圖中 X的鄰接點個數是>=4的 即比如X有個鄰接點d 只不過他與a是連通的 即DFS(a)時 會訪問到d 所以d不會是DFS樹中X的兒子;

@DELI;

@MARK: @LOC_2;
#連通無向圖G進行餘割集縮點 後的圖的性質#
SCC縮點後是DAG, BCC縮點後是樹, 而餘割集的縮點 稍微複雜; 令原連通無向圖G 進行縮點後的圖為GG (GG一定是連通無向圖); 一個性質是(G的割點 與 GG的割點)是一樣的, 也就是說 餘割集所縮成的這個點 在GG裡 一定不會是割點;
@IF(G沒有割點): GG只有1個點;
@ELSE: GG所有點的連通度 一定>= 1, 令連通度為1的點為 葉子LL, 則葉子的個數一定是>=2, 所有葉子的鄰接點(只有1個) 一定是割點 (而不是餘割集); 令所有非葉子節點為內部節點, 內部節點由{>=1個割點CC, >=0個(連通度>=2的)餘割集SS組成};
. 假如你把所有葉子去掉 剩下的圖 不一定是雙聯通的, 比如L-C-C-L(C為割點 L為葉子);
. 對於GG 你刪除任意一個割點CC後(不用考慮刪除LL/SS 因為他們一定不是割點 所以刪除他們 不影響圖的連通性) 此時圖一定分為2個連通子圖{一個是葉子節點CC, 一個是連通圖};
. . 比如G: {L1-CC1-CC2-L2, CC1-SS1-CC2}, 如果你刪除割點CC2, 則他會變成{L2}, {L1-CC1-SS1} 這兩個子圖都是連通的;

即缩点后的这个图 (如果原图有割点), 最外层节点 都是叶子节点(对应所有的(連通度為1的)餘割集), 最外層節點的鄰接點 一定是割點;
. 比如L1-C1-C2-S-C3-C4-L2, 其中L1,L2是連通度為1的餘割集 即葉子節點, C1234都是割點, S為連通度>1的餘割集

@DELI;

@MARK:@LOC_0;
對於連通無向圖G:
@IF(G沒有割點): G的割集就是{G} (只有一個割集(自身));
@ELSE: G的割集個數 ≥ 2 geq 2 ≥2 且每一個割集裡面的割點個數 ≥ 1 geq 1 ≥1;

換句話說, 如果一個割集x裡面沒有割點, 那麼G一定沒有割點 G只有一個割集x 而且G==x;

@DELI;

割點 一定同時存在於 ≥ 2 geq 2 ≥2割集裡面, 而非割點 一定只存在於 1 1 1個割集裡;

@DELI;

餘割集的鄰接點 一定是割點;
. 因為割集的定義 是把所有的割點去掉 此時每個割集之間 都是獨立的不連通的, 他的鄰接點 負責連接2個割集 即為割點;

@DELI;

餘割集表示的導出子圖 一定是連通的; 但不一定是雙連通, 比如{0-1, 0-2, 1-2, 2-3} 只有2是割點 餘割集為{0-1, 3} 其中0-1不是雙連通;

割集表示的導出子圖 一定是連通的, 但不一定是雙連通, 比如{0-1-2}的割集{0-1,1-2}都不是雙連通的, 比如{0-1-2-5-6, 1-3-5,2-3,2-4}的割集為{01, 56, 12345}他們都不是雙連通的;

@DELI;

割集裡 可以有0/1/2/...個割點;
比如{0-1}的割集為0-1沒有割點; {0-1-2}的割集0-1有1個割點(1); {0-1-3, 0-2-4, 1-2}的割集0-1-2中有2個割點(1|2);

算法

模板代碼

namespace ___Tarjan_CutPoint{
vector< vector<int> > CutSet; // 割集
//< 對於一個連通無向圖G;
//  @IF(G沒有割點):[`CutSet.size()==1`且`CutSet[0]==G所有點`];
//  @ELSE:[G的*餘割集個數*(即把G的所有割點去掉後的連通塊個數) 等於`CutSet.size()`, 對於`CutSet[i]` 他表示一個*餘割集+其鄰接點(割點)* 他裡面一定有`>=1`個割點;
vector<bool> Is_cutPoint;
stack<int> __Stk;
vector<int> __DfsId, __LowId;
int __DfsIdCounter, __DfsStartPoint;
const ___Graph * __UnDiG; // 必須為*無向圖*, 即邊的ID`e,e^1`是一對有向邊(一正一反)void __Dfs( int _cur, int _faEdge){__Stk.push( _cur);  __LowId[ _cur] = __DfsId[ _cur] = __DfsIdCounter ++;if( _faEdge != -1){ __LowId[ _cur] = __DfsId[ __UnDiG->Vertex[ _faEdge^1]];}int cc_count = 0; // 令`cur`所在的*連通子圖*為`G`, 刪除`cur`後 G會分成成`cc_count`個連通子圖;//< @IF(`cur`是割點):[`cc_count>=2`]; @ELIF(`G`只有`cur`這一個點):[`cc_count=0`]; @ELSE:[`cc_count>=1`];if( _cur != __DfsStartPoint){ ++ cc_count;}int pre = 0;for( int nex, edge = __UnDiG->Head[ _cur]; ~edge; edge = __UnDiG->Next[ edge]){if( (edge^1) == _faEdge){ continue;}nex = __UnDiG->Vertex[ edge];if( -1 == __DfsId[ nex]){__Dfs( nex, edge);if( __LowId[ nex] == __DfsId[ _cur]){++ cc_count;if( cc_count >= 2){Is_cutPoint[ _cur] = true;CutSet.push_back( {});while( true){ int c = __p();  __Stk.pop();  CutSet.back().push_back( c);  if( c == nex){ break;}}CutSet.back().push_back( _cur);//{ 如果`CutSet.back()`裡全是割點 則把他去掉;bool __isAllCutPoint = true;for( auto tt : CutSet.back()){ if( Is_cutPoint[tt] == false){ __isAllCutPoint  = false; break;}}if( __isAllCutPoint){ CutSet.pop_back();}//}}}else{ // 令cur的父節點為fa(當然DFS的起點沒有fa 但也無妨), cur在*DFS樹*的兒子節點*依次*為`{a,b,c}`(對應上面的`Dfs_id[]==-1`)//  @IF(cur為*DFS的起點*): 這裡不會進入, 即`cc_count=3`;//  @ELSE: @IF(`cc_count=4`): 這裡不會進入, 即`cc_count=4`, 刪除cur後的各個連通塊為`{fa,a,b,c}`;//         @ELSE: 這裡會進入*一次* 且此時`nex==a`, 即`cc_count=3`, 刪除cur後的各個連通塊為`{(fa|a),b,c}`; 而且`LowId[nex] < DfsId[cur]`;}MinSelf_( __LowId[_cur], __LowId[nex]);}else{MinSelf_( __LowId[_cur], __DfsId[nex]);}}if( _cur == __DfsStartPoint){CutSet.push_back( {});while( __pty() == false){ CutSet.back().push_back( __p());  __Stk.pop();}//{ 如果`CutSet.back()`裡全是割點 則把他去掉;        bool __isAllCutPoint = true;for( auto tt : CutSet.back()){ if( Is_cutPoint[tt] == false){ __isAllCutPoint  = false; break;}}if( __isAllCutPoint){ CutSet.pop_back();}//}}
}
void Work( const ___Graph & _graph){ASSERT_MSG_( "`_graph`必須為*無向圖*, 即邊的ID`e,e^1`是一對有向邊(一正一反)");__UnDiG = &_graph;  __DfsIdCounter = 0;Is_cutPoint.assign( _graph.PointsCount, false);  CutSet.clear();  __size( _graph.PointsCount);  __size( _graph.PointsCount);while( false == __pty()){ __Stk.pop();}  memset( __DfsId.data(), -1, sizeof( __DfsId[0]) * __DfsId.size());for( int i = 0; i < __UnDiG->PointsCount; ++i){if( -1 == __DfsId[ i]){__DfsStartPoint = i;  __Dfs( i, -1);}}
}
} // namespace ___Tarjan_CutPoint

注釋

求割點這個算法 是個單獨的算法, 他其實跟(求橋的算法)無關, 雖然好像看著很相像(都有LowId,DfsId,stack), 但本質上他倆是完全不同的, 因為一個是求BCC 而一個是求割集, 割集並不是BCC;
對於連通無向圖G, 他的割集 一定是其DFS樹上的子樹(這裡不是說的以x為根的子樹, 子樹的定義參見@LINK: 樹Tree) (求SCC/BCC也是依靠的這個性質), 因此有這個性質 而子樹一定只有1個(樹根) 也就是最小時間戳, 即當DFS回溯到這個(子樹的樹根)時 此時stack裡頂層的連續一段存儲的 就是這個子樹 即這個割集 即stack形如[, 割集];

令連通無向圖G的DFS樹的樹根為beg 他的割集為{S}, 定義割集Si的起點st為(即割集裡最小時間戳的節點 和SCC/BCC一樣), 有如下性質:
@IF(st不是割點): 根據性質的推理 此時有 st==beg, 此時當DFS回溯到beg時 stack裡存儲的 就是這個Si割集;
. 比如0-1-2 他的割集0-1的起點為0(不是割點); 不存在st!=beg的情況 證明參見@LINK:@LOC_0(st不是割點 說明Si割點裡面沒有割點 說明此時整個連通圖G沒有割點 即Si==G);
@ELSE: 此時st是割點 當DFS回溯到st時 此時stack裡存儲的 會形如[..., Si] 即答案在stack的頂部;

性質

割集與餘割集是一一對應;
從定義上講 是這樣的, 但是代碼模板裡的那個CutSet 他是>=2餘割集的個數;
比如1-2-3-4-5, 割點是{2,3,4}, 餘割集是{1} {5}, 所以 依照定義 割集應該是{1,2}, {4,5}, 而代碼模板裡的割集 他是{1,2} {4,5} {2,3} {3,4} 即存在(裡面全是割點)的割集, 此時你要靈活使用;
. 不過 現在代碼裡加了一個__isAllCutPoint 即把(全是割點)的割集 給去掉了已經, 因為畢竟根據定義 割集的定義 就應該是{1,2} {4,5};

刪除一個割點後 剩餘的各個連通塊的大小

定義

對於一個連通無向圖G, 求刪除一個節點後 剩下的cc_count個連通塊的各自的大小;
. 比如1-2-3-4 刪除2後 他的各個連通塊大小為{1,2};

代碼模板

G: 連通無向圖
TreeSum[ G.PointsCount] = 0;void Dfs( cur){vector<int> S; // 刪除cur後 各個連通塊的大小int cc_sum = 0;TreeSum[ _cur] += 1;for( nex){if( Dfs_id[nex] == -1){Dfs(nex);TreeSum[ _cur] += TreeSum[ nex];if( __LowId[ nex] == __DfsId[ _cur]){S.push_back( TreeSum[nex]);cc_sum += TreeSum[nex];}else{}}}if( G.PointsCount - cc_sum - 1 != 0){S.push_back( G.PointsCount - cc_sum - 1);}
}

性質

令上面代碼中if( __LowId[ nex] == __DfsId[ _cur]){為@CASE_0 他所對應的else情況為@CASE_1;
由@LINK: @LOC_1可知, 對於DFS的起點beg 他的DFS樹中的兒子節點依次為{a,b,c}(即對應Dfs_id[]==-1的情況), 那麼一定有a,b,c都是屬於@CASE_0的情況 不會是@CASE_1, 即他的Low_id一定等於0; 此時TreeSum[a,b,c]就是當前點beg的答案;
對於某點X != beg, 令他在DFS樹的兒子節點依次為{a,b,c} 令他的父節點為fa, 那麼有2種情況:
1(a與fa在同一個連通塊裡): 此時a點是屬於@CASE_1的, 你無法直接通過TreeSum來獲取a|fa這個連通塊的大小, 因此只能間接的獲得; 但此時b,c一定是@CASE_0 因此他倆連通塊大小 可以就等於TreeSum, 然後減去b,c的大小 就是a|fa的大小;
2(a,fa不在同一個連通塊裡): 此時a,b,c都是@CASE_0情況;
即代碼中的cc_sum 就等於 所有@CASE_0的連通塊的大小, 然後總點數減去他 就是fa這個連通塊的大小;

例題

模板題 @LINK: /;

筆記

EBCC/PBCC都可以順帶的求(CC連通塊), 但是SCC不能順帶求(弱連通快) 比如a<-b;

@DELI;

Some properties of the Algorithm:
+ for a connected-graph G G G, directly perform the SCC-Algorithm on it (unlike E B C C EBCC EBCC which is acted on G − E G - E G−E not G G G), then every P B C C PBCC PBCC has the property that when we at dfs(cur) where cur is not DFS-root and if(false == vis[nex]){ dfs( nex); if( low_id[nex] == dfs_id[cur]){ @Loc_0}} satisfied (low_id[nex] must always ≤ leq ≤ dfs_id[cur]); when we at @Loc_0, now all stack-points [ O , c u r , n e x , . . . ] [O, cur, nex, ...] [O,cur,nex,...] where [ c u r , n e x , . . . ] [cur, nex, ...] [cur,nex,...] forms a P B C C PBCC PBCC (cuz [root] - [cur] - [nex], so cur must be a Cut-Point;) now, you need pop out all nex, ... but keeping cur still in the stack;
__. one exception is cur == DFS_root, now it becomes [cur] - [nex] where cur maybe not a Cut-Point (cuz it has no Father-Point), but if it has at least two DFS-Unvisited-Points, i.e., [nex1]-[cur]-[nex] then cur is a Cut-Point;
+ cuz all edges are undirected, for a edge ( c u r − n e x ) (cur-nex) (cur−nex), n e x nex nex must be in the Stack if n e x nex nex has been visited by DFS, so the array On_stack can be removed.

@DELI;

涉及割点/PBCC时的解决思路

When facing a Cut-Point (PBCC) problem, you should follow the next steps:
+ if the target graph is unconnected, then divide it into all it C C CC CCs (cuz all C C CC CCs are independent to each other when handling Cut-Point), let G G G be one of its C C CC CC;
+ consider all P B C C PBCC PBCCs of G G G, rather than considering all C C CC CCs after deleting all Cut-Points from G G G;

例题

@LINK: /?articleId=128520655
設置若干出口, 使得刪除任意點後 所有點都能找到至少1個出口;

@DELI;

求cc_count 即刪除一個點後 還剩下多少個連通塊 @LINK: /?articleId=128520643;