有關圖的連通性的Tarjan演算法

2020 年 9 月 26 日
筆記

割點與橋

在一個無向連通圖中，若將某個點及其相連的邊刪除後，圖就不連通了，則這樣的點被稱為割點。
在一個無向連通圖中，若將某條邊刪除後，圖就不連通了，則這樣的邊被稱為割邊，即橋。

在一張圖中求出割點或割邊前，我們還需要兩個輔助值來得到答案。

時間戳(dfn)

在圖的dfs過程中，每個點被第一次訪問的時間排行即為時間戳。

追溯值(low)

對於每一個點，該點的追溯值為以該點為根的子樹中所有能通過一條不在搜索樹上的邊能到達該點的點的時間戳最小值。
即對於每一個點\(x\)，它的追溯值要滿足三個條件：
1)是\(x\)子樹中的某點的時間戳；
2)是通過一條不在搜索樹上的邊能回到\(x\)或其祖先的點的時間戳；
3)滿足以上條件的最小值。

那麼如何來求\(low[x]\)呢？
首先要使\(low[x]=dfn[x]\)，考慮\(x\)的每條連向子節點的邊\((x,y)\).
\(low[x]=min(low[x],low[y])\)
若\((x,y)\)不是搜索樹上的邊，則\(low[x]=min(low[x],dfn[y])\)

程式碼實現:

void tarjan(int x, int intree) {
	dfn[x] = low[x] = ++ cnt;
	for (int i = Link[x]; i; i = e[i].next) {
		int y = e[i].to;
		if (!tarjan[y]) {
			tarjan(y, i);	
			low[x] = min(low[x], low[y]);
		}
		else if (i != (intree ^ 1)) low[x] = min(low[x], dfn[y]);
	}
}
//以下內容在main函數中：
tot = 1; 
for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i);

在這份程式碼中，為了方便記錄某點到子節點的邊編號，要將\(tot\)的初值賦為\(1\)；以及異或(^)的優先順序沒有!=高，所以要在\(intree^1\)上加括弧提高優先順序

得到這些值，我們就可以用來判斷某點/邊是否為割點/邊

割邊的判定法則

考慮一條邊\((x,y)\)，\(y\)是\(x\)的子節點，若\(low[y]<dfn[x]\)，即在\(x\)的子樹中，沒有任何一個點能不通過\((x,y)\)到\(x\)及其祖先上，則說明這條邊是割邊。
以HLOJ的模板題為例：

#include<bits/stdc++.h>
using namespace std;

const int N = 100009, M = 300009;
int n, m, Link[N], tot = 1, dfn[N], low[N], cnt;
struct edge{int next, to, bridge;} e[M << 1];
struct answer{int x, y;} ans[M];

inline void add(int x, int y) {e[++ tot].next = Link[x]; Link[x] = tot; e[tot].to = y;}

void tarjan(int x, int intree) {
	dfn[x] = low[x] = ++ cnt;
	for (int i = Link[x]; i; i = e[i].next) {
		int y = e[i].to;
		if (!dfn[y]) {
			tarjan(y, i);
			low[x] = min(low[x], low[y]);
			if (low[y] > dfn[x]) e[i].bridge = e[i ^ 1].bridge = 1;
		}
		else if (i != (intree ^ 1)) low[x] = min(low[x], dfn[y]);
	}
}

inline bool cmp(answer x, answer y) {return x.x == y.x ? x.y < y.y : x.x < y.x;}

int main() {
  freopen("danger.in", "r", stdin);
  freopen("danger.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++ i) {
    	int x, y;
    	scanf("%d%d", &x, &y);
    	add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i, 0);
    cnt = 0;
    for (int i = 2; i < tot; i += 2) if (e[i].bridge) ans[++ cnt].x = min(e[i ^ 1].to, e[i].to), ans[cnt].y = max(e[i ^ 1].to, e[i].to);
	sort(ans + 1, ans + cnt + 1, cmp);
	for (int i = 1; i <= cnt; ++ i) printf("%d %d\n", ans[i].x, ans[i].y);
    return 0;
}

由於上文提到\(tot\)從\(1\)開始，所以在得出割邊是要從tot=2開始枚舉。

割點的判定法則

類似於判定割邊，只要滿足\(low[y]<=dfn[x]\)的點即為割點。
求割點的方法類似，故不再贅述。

兩道例題

BZOJ1123 BLO

題意

給出一張無向連通圖，求去掉每一個點後有多少有序點對不連通
\((n<=100000,m<=500000)\)

題解

若某一個點不是割點，即刪除該點後圖仍然連通，則只有該點產生\(2(n-1)\)的貢獻；
考慮某一點\(x\)是割點，刪除它後我們把圖分成三部分考慮：
1)\(x\)本身
2)\(x\)子樹內除了\(x\)的點
3)\(x\)子樹外的點
這三者的大小分別為\(1\),\(size[y]\),\(n-1-\sum size[y]\).
那麼答案為\(\sum size[y]*(n-size[y])+(n-1)+(\sum size[y])*(n-1-\sum size[y])\)