【模板】連通分量

名詞解釋

連通分量：數量最多、擴展範圍最大
割點：把這個點拔掉會增加連通塊數量
橋：把這個邊拔掉會增加連通塊數量
無向連通分量
- 橋連通分量（邊雙連通分量）：一個連通分量內，拔掉任一邊連通塊數量不會增加
- 點雙連通分量：一個連通分量內，拔掉任一點連通塊數量不會增加
有向圖連通分量
- 強連通分量：一個連通分量內，a 能到 b、b 能到 a

DFS Tree

把一張圖 DFS，邊可以分成四種：

Tree Edge：DFS 過程中經過的邊。DFS 時，走向沒走過的臨點的鄰邊都是 Tree Edge。
Back Edge：通向祖先的鄰邊。
Forward Edge：不再 DFS Tree 上，通向子樹的鄰邊。
Cross Edge：通向不存在父子關係的點的鄰邊。

在 DFS 時，遇到走訪過的邊就是下面三種之一。並且無向圖只存在 Tree Edge 和 Back Edge（Forward Edge 因為無向等同於 Back Edge；u 若存在 Cross Edge 連到 v，那在 v 時就應改把這條邊當成 Tree Edge）。所以討論連通的時候，只需要討論子孫和祖先的關係。

Tarjan's BCC

割點

在 DFS Tree 上當一個點被拔掉，子孫還想要跟祖先點互通有無，那就只能透過 Back Edge 了。如果這個子樹中有一條 Back Edge 可以回到任一個祖先，那點被拔掉就不會影響該子樹根祖先互通。反之若其中一個子樹不存在 Back Edge 可以連回祖先，那該點就是割點。

low 函數

我們可以記錄該點的子孫通過 Back Edge 最上面可以連到哪裡，這樣祖先們都能用它該點是否可以走到自己上面。我們稱它為 \(low(u)\)。當走 Tree Edge 到子節點，可以直接拿他的 \(low\)；或是走 Back Edge 到祖先，則拿他的深度。

特判根

沒有人可以透過 Back Edge 走到根上面。根是割點，若且唯若根有兩個以上的子節點。

Tarjan 求割點實作

維護 dep、low
檢查該點是否為割點，特判根。

vector<int> G[N];
int isap[N], low[N], dep[N];

void dfs (int u, int p){
    int child = 0;
    low[u] = dep[u] = low[p]++;
    for (auto v: G[u]){
        if (v == p) continue;
        if (dep[v]){
            low[u] = min(low[u], dep[v]);
        }
        else{
            dfs(v,u);
            child++;
            low[u] = min(low[u], low[v]);
            if (low[v] >= dep[u]){
                isap[u] = 1;
            }
        }
    }
    if (u==p && child<=1) isap[u] = 0;
}

點雙連通分量

維護一個 stack，我後面都是子孫並且跟我是同一個 BCC。如果我是這個 BCC 裏最淺的點，就把我以後的東西都 pop 出來，作為我 BCC 裡面的點。如果該點是割點，記得放回去（最淺的那個點一定是割點），因為割點還會屬於其他 BCC。

當沒有兒子的時候需要特判。

vector<int> G[N];

int low[N], dep[N], n, m, bcnt;
vector<int> st, memb[N];
void dfs (int u, int p){
    if (u == p && G[u].size()<1){
        memb[bcnt++].pb(u);
        return;
    }
    low[u] = dep[u] = dep[p]+1;
    st.pb(u);
    for (auto v: G[u]){
        if (v == p) continue;
        if (dep[v]){
            low[u] = min(low[u], dep[v]);
        }
        else{
            dfs(v,u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dep[u]){
                bcnt++;
                while(1){
                    memb[bcnt].pb(st.back());
                    if (st.back() == u) break;
                    st.pop_back();
                }
            }
        }
    }
}

橋

當一條走往子樹的邊被拔掉，子樹還想跟自己互通，就要有一條 Back Edge 連到自己或祖先。

實作

維護 dep、low
確認連向子樹的邊是不是橋（子樹有沒有任一個節點有 Back Edge 連回自己或祖先）
子節點只要不走過來的邊就行

vector<int> G[N];
struct Edge {int u, v;};
vector<Edge> edges;

void add_edge (int u, int v)
{
	G[u].pb(edges.size());
	edges.pb({u,v});
	G[v].pb(edges.size());
	edges.pb({v,u});
}

int d[N], l[N], timestamp, bridge_cnt;
void tarjan (int u, int from)
{
	d[u] = l[u] = ++timestamp;
	for (auto e: G[u])
	{
		int v = edges[e].v;
		if (!d[v])
		{
			tarjan(v,e^1);
			l[u] = min(l[u], l[v]);	
			if (l[v] > d[u])
			{
				bridge_cnt++;
			}
		}
		else if (e!=from)
		{
			l[u] = min(l[u], d[v]);
		}
	}
}

總有一天會用到的筆記