tarjan 算法学习笔记

· · 算法·理论

前言

虽然学过了,但学得不是很清楚。故而洗点重来。

PS:请自行画图举例,这能帮助你更好地记住并掌握才不是因为懒得画图呢

算法部分

tarjan 的两个核心数组

$low_i$:表示 $i$ 点不经过连向父亲的边能到达的 dfs 序最小的点的 dfs 序(暂时这样定义,这可以引申出后面的更好定义)。 ## tarjan 求割边 我最开始学的是 tarjan 求强连通分量,但显然割边更适合入门。 ### 定义 割边:对于一个无向图内的边,如果删去这条边后图的连通块数增加,那么这条边是割边。 ### 做法 多个连通块的情况就是每个连通块的和,所以我们只考虑一个连通块的情况。 对一个无向图,先求出它的一个 dfs 树。容易发现,非树边都不会是割边,因为不需要它们所有的点也能形成一个树。 先不考虑怎么求 $low$,假设它是封装好的函数,可以直接调用。 考虑怎么用这两个数组判断一条树边是否是割边。设这条树边连接的两个点为 $u$ 和 $fa$($fa$ 为 $u$ 的父亲)。当我们断开这条边后,树就会变成两个,我们只需要找到一条边连接 $u$ 的子树和其它点形成的连通块就能证明这条边不是割边。 ![](https://cdn.luogu.com.cn/upload/image_hosting/w758kflc.png) 图中 $u=6$,加粗的点和不加粗的点分别在两个不同的连通块内 如果存在一条非树边,连接 $u$ 的子树和其它点形成的连通块,那么 $low_u<dfn_u$。因为 $u$ 的祖先中一定有根节点,其 dfs 序为 $1$,这条边的存在会使 $low_u=1$。 否则 $low_u=dfn_u$,因为 $u$ 子树内 dfs 序最小的数是 $u$。 现在思考如何求出 $low$ 数组。发现这个定义不能简单地通过儿子转移,于是把它换成更好转移的定义。 设 $low_i$ 表示**至多经过一条非树边并且只经过 $i$ 子树内的树边所能到达的最小 dfs 序**。 这样的 $low$ 值实际上就是 $dfn_u$ 和子树连出的非树边连向点的 dfs 序的最小值。可以发现这样的 $low$ 仍然满足仅当 $low_u<dfn_u$ 时,边 $(u,fa)$ 不为割边。 这是由于 dfs 树的性质,非树边只会连接有直接祖先关系的点。这使得非树边要么连接的是子树内的点,要么连接的是 dfs 序更小的点。也就是说,从非树边跳两次是不必要的。如果连接的是子树内的点,那么完全可以从树边走过去;如果连接的是子树外的点,那么已经满足条件,无需再跳。 而这样的定义也让我们避免了从子树外通过树边走到 $(u,fa)$ 的情况。 实现看代码。 ### 代码 [例题](https://www.luogu.com.cn/problem/AT_abc075_c) ```cpp void tarjan(int pos, int fa) { dfn[pos] = low[pos] = ++tot; for(int i = head[pos]; i; i = e[i].nxt) { if(!dfn[e[i].to]) {//树边 tarjan(e[i].to, pos); low[pos] = min(low[pos], low[e[i].to]); if(low[e[i].to] == dfn[e[i].to])ans++; } else if(e[i].to != fa)low[pos] = min(low[pos], dfn[e[i].to]);//树外边 } } ``` ## tarjan 求割点 ### 定义 割边:对于一个无向图内的点,如果删去这个点后图的连通块数增加,那么这个点是割点。 ### 做法 与求割边类似,对于非根节点 $u$,如果存在一个儿子 $v$ 使得 $low_v=dfn_v$ 或 $low_v=dfn_u$,那么点 $u$ 是割点。 $low$ 的优秀定义再次帮助了我们。由于非树边只会走一条,所以我们可以轻松看出当前的 $low$ 是否经过了点 $u$。 对于根节点,由于无向图的 dfs 树的非树边只会连接祖先后代,而根节点没有祖先,所以只需要看根节点的子树数量是否大于 $1$ 即可。 你也可以通过把边当作点,点当作边的方式求解。 ### 代码 [例题](https://www.luogu.com.cn/problem/P3388) ```cpp void tarjan(int pos, int root) { dfn[pos] = low[pos] = ++cnt; for (int i = head[pos]; i; i = e[i].nxt) { if (!dfn[e[i].to]) { if (root == pos)rt++; tarjan(e[i].to, root); if ((low[e[i].to] == dfn[pos] || low[e[i].to] == dfn[e[i].to]) && root != pos)cut[pos] = 1; low[pos] = min(low[pos], low[e[i].to]); } else low[pos] = min(low[pos], dfn[e[i].to]); } if (rt >= 2 && root == pos)cut[pos] = 1; } ``` ## tarjan 求边双连通分量 ### 定义 边双连通分量:对于一个无向图,不存在桥的极大连通子图即为一个边双连通分量。 ### 做法 将所有遍历到的点压入一个栈内,遍历是按 dfs 序的,所以入栈也是按 dfs 序的。当遇到 $dfn_u=low_u$ 时,代表边 $(u,fa)$ 是一条割边,不能出现在边双里面。 不断出栈直到弹出点 $u$,这些同一次出栈的点在一个边双里面。这是因为在 $u$ 后入栈的点都在其子树内,而子树内的割边所连的点都已经全部出栈。 ### 代码 [例题](https://www.luogu.com.cn/problem/P8436) ```cpp void tarjan(int pos, int las) { dfn[pos] = low[pos] = ++cnt; st.push(pos); for(int i = head[pos]; i; i = e[i].nxt) { if(!dfn[e[i].to]) { tarjan(e[i].to, i); low[pos] = min(low[pos], low[e[i].to]); } else if(i != (las ^ 1))low[pos] = min(low[pos], dfn[e[i].to]); //本题可能有重边,las 和 las ^ 1 分别表示一条无向边的两个方向 } if(dfn[pos] == low[pos]) { ans[++scc].push_back(pos); while (pos != st.top()) { ans[scc].push_back(st.top()); st.pop(); } st.pop(); } } ``` ## tarjan 求点双连通分量 ### 定义 点双连通分量:对于一个无向图,不存在割点的极大连通子图即为一个点双连通分量。 ### 做法 与边双连通分量不同的是,整个图的割点可以出现在点双连通分量中多次。 ![](https://cdn.luogu.com.cn/upload/image_hosting/o6wz1rdq.png) 上图中,红边为树外边,绿色部分和蓝色部分分别为两个点双连通分量。 原因是原图的割边加入边双中就会使连接的两个点加入边双,从而导致割边在边双中也是割边;而原图的割点加入点双中并不会使和它连接的所有点加入点双。 对于一个点 $u$,当遇到儿子 $v$ 满足 $low_v=dfn_v$ 或 $low_v=dfn_u$ 时,子树 $v$ 会使 $u$ 变成割点。因此不断出栈直至弹出 $v$,这些点和 $u$ 构成一个点双。 对于根节点,无需特殊判断,直接当作割点即可。这是因为当根节点不为割点时,我们也需要把剩下的点塞进一个点双里面。 ### 代码 [例题](https://www.luogu.com.cn/problem/P8435) ```cpp void tarjan(int pos, int las) { //本题还需要判断自环 dfn[pos] = low[pos] = ++cnt; st.push(pos); for(int i = head[pos]; i; i = e[i].nxt) { if(!dfn[e[i].to]) { tarjan(e[i].to, i); low[pos] = min(low[pos], low[e[i].to]); if(low[e[i].to] == dfn[e[i].to] || low[e[i].to] == dfn[pos]) {//对于子树 e[i].to,pos 是割点或根 ans[++scc].push_back(pos); ans[scc].push_back(e[i].to); while(e[i].to != st.top()) {//弹出 e[i].to 的子树 ans[scc].push_back(st.top()); st.pop(); } st.pop(); } } else if(i != (las ^ 1))low[pos] = min(low[pos], dfn[e[i].to]); } if(!las && !head[pos])ans[++scc].push_back(pos);//独立点 } ``` ## tarjan 求强连通分量 ### 定义 强连通分量:对于一个有向图,任意两点能够互相到达的极大连通子图为强连通分量。 ### 做法 重新定义 $low_i$,表示和 $i$ 强连通的,dfs 序最小的点的 dfs 序。 延续前面的做法,考虑在一个强连通分量内,选出一个点 $u$ 作为代表,满足 $low_u=dfn_u$。 对于所有在 $u$ 子树内部连的边,走向的 dfs 序最小的点唯一,就是 $u$。对于 $u$ 子树内向外部连的边,如果连接的是 $u$ 的祖先,那么这些点就和祖先强连通,与前提矛盾。所以强连通分量内不会出现向 $u$ 的祖先连的边。 但是有向图的 dfs 树还有可能向以前访问过的其它点连边。假设该边为 $(u,v)$。如果 $v$ 没有一种路径可以到达它和 $u$ 的共同祖先,也就是不强连通。这就导致了 $low_u<dfn_u$,在强连通分量内找不到代表。 这是容易解决的。如果 $v$ 不和 $u、v$ 的最近公共祖先强连通,那么在处理 $u$ 之前,$v$ 所属的强连通分量就应该统计过了。只需要记录哪些点被统计过,不用这些点转移 $low$ 即可。 由于强连通具有传递性,所以不存在一个点同时在两个强连通分量内的情况。 事实上,在下面的示例代码中,$low$ 的含义和我们这里定义的并不一样,它是至多经过一条非树边并且只经过 $i$ 子树内的树边所能互相到达的最小 dfs 序。 按照我们的定义,`else if (vis[e[i].to])low[pos] = min(low[pos], dfn[e[i].to]);` 应为 `else if (vis[e[i].to])low[pos] = min(low[pos], low[e[i].to]);`。 但两者都是正确的,原因留给读者自己思考。 ### 代码 [例题](https://www.luogu.com.cn/problem/B3609) ```cpp void tarjan(int pos) { dfn[pos] = low[pos] = ++cnt; vis[pos] = 1; st.push(pos); for (int i = head[pos]; i; i = e[i].nxt) { if (!dfn[e[i].to]) { tarjan(e[i].to); low[pos] = min(low[pos], low[e[i].to]); } else if (vis[e[i].to])low[pos] = min(low[pos], dfn[e[i].to]); } if (dfn[pos] == low[pos]) { ans[++scc].push_back(pos); belong[pos] = scc; vis[pos] = 0; while (st.top() != pos) { ans[scc].push_back(st.top()); belong[st.top()] = scc; vis[st.top()] = 0; st.pop(); } st.pop(); } } ``` ## 缩点 说了这么多,这几个连通分量到底有什么用呢? 如果题目的性质能让我们把图中的边双连通分量/点双连通分量/强连通分量视作一个点,那么这个图会有非常好的性质。 下面我们用强连通分量举例: 如下图,每种颜色所圈的都是一个强连通分量。 ![](https://cdn.luogu.com.cn/upload/image_hosting/4akcce2i.png) 缩点后: ![](https://cdn.luogu.com.cn/upload/image_hosting/lv2kcjzb.png) 发现缩点之后形成了一个 DAG(有向无环图)。因为若有环,则环上的强连通分量是强连通的,不符合前提。 同理,边双连通分量缩点后会形成一棵树。 ### 代码 [例题](https://www.luogu.com.cn/problem/P3387) 强连通分量缩点后直接在 DAG 上处理即可。 ```cpp #include<bits/stdc++.h> using namespace std; const int M = 100010, N = 10010; int n, m, head[N], tot, cnt, low[N], dfn[N], scc, belong[N], sum[N], val[N], in[N], dp[N], ans; stack<int>st; bool vis[N]; struct Node { int to, nxt; } a[M]; struct node { int u, v; } b[M]; void add(int u, int v) { a[++tot].to = v; a[tot].nxt = head[u]; head[u] = tot; } void tarjan(int pos) { dfn[pos] = low[pos] = ++cnt; vis[pos] = 1; st.push(pos); for (int i = head[pos]; i; i = a[i].nxt) { if (!dfn[a[i].to]) { tarjan(a[i].to); low[pos] = min(low[pos], low[a[i].to]); } else if (vis[a[i].to])low[pos] = min(low[pos], dfn[a[i].to]); } if (dfn[pos] == low[pos]) { scc++; int now = 0; while (now != pos) { now = st.top(); belong[now] = scc; sum[scc] += val[now]; st.pop(); } } } void init() { memset(head, 0, sizeof(head)); memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); cnt = scc = tot = 0; } int main() { n = read(); m = read(); for (int i = 1; i <= n; i++)val[i] = read(); for (int i = 1; i <= m; i++) { b[i].u = read(); b[i].v = read(); add(b[i].u, b[i].v); } for (int i = 1; i <= n; i++)if (!dfn[i])tarjan(i); init(); for (int i = 1; i <= m; i++) { if (belong[b[i].u] == belong[b[i].v])continue; add(belong[b[i].u], belong[b[i].v]); ++in[belong[b[i].v]]; } queue<int>q; for (int i = 1; i <= n; i++) if (!in[i]) { q.push(i); dp[i] = sum[i]; } while (!q.empty()) { int now = q.front(); q.pop(); for (int i = head[now]; i; i = a[i].nxt) { int v = a[i].to; in[v]--; dp[v] = max(dp[now] + sum[v], dp[v]); if (!in[v])q.push(v); } } for (int i = 1; i <= n; i++)ans = max(dp[i], ans); write(ans); return 0; } ``` ## tarjan 求 2-SAT ### [定义](https://www.luogu.com.cn/problem/P4782) ### 做法 满足 $x_i \vee x_j$ 等价于满足:若 $\neg x_i$,则 $x_j$;若 $\neg x_j$ 则 $x_i$。 对每个变量 $x_i$,我们在图上建两个点 $x_i$ 和 $\neg x_i$。将若 $\neg x_i$,则 $x_j$ 的条件转化为连接 $\neg x_i$ 和 $x_j$ 的有向边。这样我们的图就具有了推导的意义——如果在图上能从 $a$ 到 $b$,那么必然能从 $a$ 推出 $b$。 考虑什么情况下无解。显然如果 $\neg x$ 和 $x$ 能够互相到达那么是无解的。可以用 tarjan 求强连通分量来判断。 如果有解又该怎么找到一组解呢?如果 $\neg x$ 能够到达 $x$,那么必然选择 $x$ 为真,否则矛盾。反之亦然。可以通过缩点后的拓扑序来判断。 实际上,通过 tarjan 算法求出的强连通分量编号即为其缩点后的反拓扑序。想一想,为什么? ### 代码: ```cpp signed main() { for(int i = 1; i <= m; i++) { int u = read(), a = read(), v = read(), b = read(); if(a && b)add(u + n, v), add(v + n, u); else if(a)add(u + n, v + n), add(v, u); else if(b)add(v + n, u + n), add(u, v); else add(u, v + n), add(v, u + n); } for(int i = 1; i <= 2 * n; i++)if(!dfn[i])tarjan(i); bool flag = 0; for(int i = 1; i <= n; i++) { if(belong[i] == belong[i + n])flag = 1; ans[i] = (belong[i] < belong[i + n]); } if(flag)puts("IMPOSSIBLE"); else { puts("POSSIBLE"); for(int i = 1; i <= n; i++) { putchar('0' + ans[i]); putchar(' '); } } return 0; } ``` # 例题: [P3469 [POI2008] BLO-Blockade](https://www.luogu.com.cn/problem/P3469) [P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G](https://www.luogu.com.cn/problem/P2341) [ P2272 [ZJOI2007] 最大半连通子图 ](https://www.luogu.com.cn/problem/P2272) ## 绘图工具 [Graph Editor](https://csacademy.com/app/graph_editor/) [智绘教](https://github.com/Alan-CRL/Intelligent-Drawing-Teaching)