changed a year ago  
Published Linked with GitHub

SCC

Strongly Connected Components，中文即"強連通分量"
意旨為在一個強連通分量中，任意兩點均有大於一種路徑可到達，也就是在一個SCC中不管從哪裡開始，都可以走完全部的點。

或是

像這樣內部可互相抵達的圈圈我們可以把它縮成一個點，意即縮點。


這方法會在某些題目上用到，像是這題。題目要求一個國王的統治區域內要任兩點均可抵達，並且編號其王國，這在作法上就可以用SCC來解決:把任兩點可以抵達的區域縮點，接著把所有縮點編號，就大功告成了。

有兩種演算法可以做到分別為:

  • Tarjan’s SCC Algorithm
  • Kosaraju’s Algorithm

Tarjan's SCC Algorithm

此演算法重點在維護三個變數，分別為dfn、up、stk

  • dfn : 在dfs的時候邊紀錄走過(遞迴)的順序，意即dfs number，簡稱dfn
  • up : 在每個點都維護一個up值，代表我的子樹能繞上去到最上面的祖先的編號(dfn)是多少
  • stk : 設一個Stack來記錄待合成SCC的節點，照遞迴順序push in

接著，在遞迴子樹的時候 :

  • 如果遇到沒有走過的點時，就dfs下去，並且更新我的UP值
  • 如果遇到之前走過的點時，有兩種情況 :
    • 該點已被構成SCC(已pop出stack) : 直接略過，不能更新到UP，因為其他SCC是不能繞到自己SCC祖先的，否則會構成更大的SCC，先前建立的SCC就不合理。
    • 該點還沒被構成SCC(還在stack裡) : 直接更新，因為之前已經走過了，直接拿UP來用就好。

最後遞迴完所有子樹節點時，判斷該點的dfn有沒有等於UP，如果dfn==up代表該點不能再繞上去了，表示找到一個SCC，並且該點為Root，開始pop出stack裡的節點作為該SCC的元素直到當前節點，因為子樹有可能有其他的SCC，所以stack的用意就是維護在遞迴時按照順序的節點，在pop出節點時也才會是照遞迴順序返pop出(子樹的SCC節點已被pop出)。

至於為什麼不能在繞上去就是一個SCC的Root呢，假設一個節點可以繞上去，就代表走完這條路可以回到該點走別條路，符合SCC的性質，如果不能再繞上去說明該點的父節點只能往下，不符合SCC性質，不能合併到下面的SCC，所以在交界處的節點就會是dfn==up。





































const int MAXN = 100005;
vector<int> Graph[MAXN];
stack<int> stk;
bool instk[MAXN];
int Dfn[MAXN], Up[MAXN], sccId[MAXN], dfn, sccNumber;

void tarjan(int now) {
    Dfn[now] = Up[now] = ++dfn; //給予dfn及初始化up(能回到最上的祖先節點編號，預設為自己)

    stk.push(now); // push into stack
    instk[now] = true; // mark

    for (auto i : Graph[now]) {
        if (!instk[i] && Dfn[i]) continue; // 如果被走過且不在stack裡代表已經是其他SCC
        
        // 剩下的只有可能是還沒被走過或還在stack裡，代表待合成SCC
        if (!Dfn[i]) tarjan(i); // 如果還沒被走過就先遍歷
        Up[now] = min(Up[now], Up[i]); // 更新我能回到最上祖先節點的編號(dfn)
    }

    if (Dfn[now] == Up[now]) { // 如果遍歷完全部的子樹，我能回到最上的祖先編號為自己的話，代表我的子樹是一個SCC且我是root
        sccNumber++; // 建立一個新的SCC
        int x;
        do {
            x = stk.top();
            stk.pop(); // pop from stack
            instk[x] = false; // unmark
            sccId[x] = sccNumber; // 更新子樹的SCC編號
        } while (x != now);    // 更新所有子節點直到Root
    }
}

//----------main----------
for (int i = 1; i <= n; i++) {
    if (!dfn[i]) tarjan(i);
}

Kosaraju's Algorithm

此演算法會用到兩個dfs，分別是順向和反向

  • 第一次dfs(順向) : 在結束子樹遞迴return前，紀錄該點點到一個Stack裡。
  • 第二次dfs(反向) : 從Stack的top開始，利用反向圖遞迴，遞迴到的元素即為一個SCC。

原理 :
因為一個SCC不管是正向圖或是反向圖都不會影響其性質(兩點間皆有至少一路徑可達)，可互相走到的點還是可以走到(想成倒退走)，所以正反dfs都可達到的點群即為一個SCC。

在第一個dfs時，要找到最上游(圖左邊)的節點編號，依序往下游(圖右邊)排列，Stack的Top也就是Root，這樣才能在第二個dfs時，從下游(正向圖上游)開始建立SCC，讓在之後建立SCC時能把更下游的節點(已被建立為SCC的節點)篩掉，此動作跟Tarjan把子樹先pop出stack有異曲同工之妙。

Original graph


After reversing the original graph:

靠近Root的點(先走到的點)在正向圖中為上游，在反向圖中就會變成下游(原本是我走向別人變成別人走向我)，本來可以從上游SCC走到下游SCC，但在反向圖中，唯一一條能走向別的SCC的路被堵住了(變成反向了)，所以從Stack[Top]開始走第二次dfs時只要能走到的點就是同一個SCC。














































#define MAXN 100005

stack<int> stk;               //stack
vector<int> Graph[MAXN];      //graph
vector<int> Rev_Graph[MAXN];  //reverse graph
bool vis[MAXN];               //is visited
int scc[MAXN];                //i's scc 
int sccid;                    //scc number

void dfs1(int now){
	vis[now]=true;
	for(auto i:Graph[now]){
		if(!vis[i]) dfs1(i);
	}
	stk.push(now);  //push now in stack before return
}

void dfs2(int now){
	vis[now]=true;
	scc[now]=sccid;  //conbine to scc
	for(auto i:Rev_Graph[now]){
		if(!vis[i]) dfs2(i);
	}
}

int main(){
	int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int u,v;
		cin >> u >> v;
		Graph[u].push_back(v);
		Rev_Graph[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]) dfs1(i); //do dfs1 of all elements
	}
	memset(vis,0,sizeof(vis)); //reset vis array
	while(!stk.empty()){  //iterate all elements of stack
		int x=stk.top();stk.pop();
		if(vis[x]) continue; //skip node which has been combined to another scc
		sccid++;
		dfs2(x);
	}
}

Cut Point

如果一個點不是割點，其所有子樹都可以繞到此點的祖先，換句話說，只要有一個子樹不能繞到此點的祖先，那該點就是割點

在dfs時，記錄一個時間戳記(dfn)，用來表示此節點的祖先編號，因為祖先一定會先遍歷到，dfn較小，可用來判斷能否繞上去

如果要走的點的dfn已經被賦予值，代表該點為祖先，直接更新low[now]，取min:能繞上去的最小祖先，如果沒有被遍歷過，代表該點為子樹，就往下dfs，對於每個未走過子樹，dfs完後檢查該子樹能否走到此點的祖先(if low[i]<=dfn[now]代表該點能走到的最小祖先有比此點還上面)，如果不能，就代表此點為割點，因為第一段的結論:"只要有一個子樹不能繞到此點的祖先，那該點就是割點"

唯一要注意的是根結點，因為其他節點都有father，唯獨根結點沒有，其他節點當割點時可以切割father以上的節點和割點以下的節點，但因為根結點沒有father，所以必須要兩個以上的子樹才能成為割點


















































#define MAXN 100005
vector<int> Graph[MAXN];
int dfn[MAXN],low[MAXN],root,idx;
bool is_cut_point[MAXN];

void tarjan(int now){
	dfn[now]=low[now]=++idx;
	//dfn為dfs時的順序
	//low為該點能繞到dfn最小祖先的節點編號
	
	int up=0;  //為能繞上去的路徑數量
	for(auto i:Graph[now]){
		if(!dfn[i]){  //如果沒有走過就往下走
			tarjan(i);
			low[now]=min(low[now],low[i]);  //找該子樹能繞上去最小的dfn編號，更新low[now]
            
			if(low[i]>=dfn[now]){  //如果不能繞上去
				up++;
                
				//如果now不為根結點:只要有一個點不能繞上去，該點即為切點
				//如果now  為根結點:有兩個以上不能繞上去的子樹才能為切點
				if(now!=root || up>=2) is_cut_point[now]=true;
			}
		}else{ //有走過
                       //只能拿dfn來更新，不能拿low，因為無向圖可以往fa走，會一直追朔到起點
			low[now]=min(low[now],dfn[i]);  //找最小dfn的祖先，更新low[now]
		}
	}
}


signed main(){
    
    int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int u,v;
		cin >> u >> v;
		Graph[u].push_back(v);
		Graph[v].push_back(u);
	}
	
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			root=i;
			tarjan(i);
		}
	}
}

學習紀錄

Q : 為什麼在Tarjan演算法中如遇到該點已走過時只需用dfn[i]更新就好了，要取min的話，用low[i]來更新不是更好嗎?

A : 因為在Tarjan的重點在於「能不能繞上去」，而不是「能繞上去最高到哪裡」，因此用low[i]或dfn[i]來更新都是可以的。另外一個觀察是dfn[i]一定會比當前的dfn[now]小，因為dfn是按走過的點嚴格遞增的，所以只要走到走過的點就都會是能繞上去的祖先，還有一個前提是圖要是有向圖。

這題最初的想法 : 先把所有入度為0的點都dfs一次，接著再看剩下沒被dfs到的就代表是環
但此做法並非最佳解，可能會有以下狀況

有可能會先搜尋到下面三個點，就變成要跑兩次。

Select a repo