# 前言虽然学过了，但学得不是很清楚。故而洗点重来。 PS：请自行画图举例，这能帮助你更好地记住并掌握~~才不是因为懒得画图呢~~。 # 算法部分 ## tarjan 的两个核心数组 $dfn_i$：表示 $i$ 点的 dfs 序。 $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= 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 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; stackst; 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]]; } queueq; 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)