dSCC(Strongly Connected Component)
========
Graph
--------
###互相連接的圖(graph/component)
- 若是在兩圖間存在成對的節點(vertex)，且兩節點存在至少一條連接路徑 & 不可再加進其他節點，則兩圖互相連接。
###關鍵節點(articulation(cut-vertex))
- 移除關鍵節點，則圖一分為二。
###關鍵路徑(bridge(cut-edge))
- 同關鍵節點，移除關鍵路徑，則圖一分為二。
Articulation/Bridge
--------
###在圖中尋找關鍵節點
- 因為移除關鍵節點後圖會分離，最簡單直接的方式就是每個點都移除看看。
- 也就是 V 次 DFS => O(V*(V+E)) 這明顯太慢了。
- 若不是關鍵節點，則可以找到替代路徑。
- 那麼只要尋找環，就能達到目的。
- 方法也是採用 DFS ，但只要 O(V+E) 的時間複雜度。
###概念
- 若節點 u 是關鍵節點。
- 則 u 的子節點不會連接到u之前的節點。
- 或 u 是 root & 至少有兩個子節點。
- 否則僅為節點。
- 兩關鍵節點間的直接連接路徑，即為關鍵路徑。
###演算法
- 使用變數
- dfn[i]-時間標記，DFS時初次訪問此節點的順序
- low[i]=min(dfn[i], lowest low[j])-可以理解為此節點隸屬於哪一關鍵節點之下
- 關鍵節點
- u 的子節點不會連接到u之前的節點 -> dfn[i]<=low[j] & j 是 i 的子節點
- u 是 root & 至少有兩個子節點 -> count child>=2
- 關鍵路徑
- 兩關鍵節點 i 、 j -> dfn[u]Code
~~~{.c }
void dfs(int pre , int cur){
int child = 0;
bool cut_vertex = false;
low[cur] = dfn[cur] = ++cnt_dfn;
for(int &i : edge[cur]){
if(!dfn[i]){
dfs(cur , i);
low[cur] = min(low[cur] , low[i]);
++child;
if(low[i] >= dfn[cur]) cut_vertex = true;
}
else if(i != pre) low[cur] = min(low[cur] , dfn[i]);
}
if(cut_vertex && (child > 1 || pre != -1)) ++ans;
}
~~~
Strongly Connected Component(SCC)
--------
- 因為一張圖上有環，演算法的效率會變差。
- 所以我們要想辦法收縮所有的SCC跟環，這樣圖就變成一顆樹，或有向無環圖（DAG）了。
###Tarjan
- Tarjan就是一種演算法，可以用來找到環的個數
- 演算法中會用到前段的概念，請務必先理解
- Code
~~~{.c }
void Tarjan(int cur){
int top;
low[cur] = dfn[cur] = ++cnt_dfn;
stack.push_back(cur);
in_stack[cur] = true;
for(int &i : edge[cur]){
if(!dfn[i]){
dfs(i);
low[cur] = min(low[cur] , low[i]);
}
else if(in_stack[i]) low[cur] = min(low[cur] , dfn[i]);
}
if(dfn[cur] == low[cur]){
do{
top = stack.top();
stack.pop();
in_stack[top] = false;
} while(top != cur);
++ans;
}
}
~~~
