有关图的连通性的Tarjan算法

割点与桥

在一个无向连通图中，若将某个点及其相连的边删除后，图就不连通了，则这样的点被称为割点。

在一个无向连通图中，若将某条边删除后，图就不连通了，则这样的边被称为割边，即桥。

在一张图中求出割点或割边前，我们还需要两个辅助值来得到答案。

时间戳(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])\)

巴特西