图论学习条记2

请先阅读图论学习条记 1。
在这篇文章里，我们将继续从前 tarjan 求解的强连通分量和双连通分量，讲授其缩点相干内容。
也会讲授一些特殊的图：基环树与神仙掌图、最小树形图。
缩点

我们知道，将强连通分量、双连通分量缩点之后会形成一棵树。
在学术上，我们将边双连通分量缩点之后的树称为 Bridge Tree，点双连通分量缩点之后的树称为 Block-Cut Tree，强连通分量缩点之后的树称为 SCC DAG。
缩点除了写法没什么好讲的，而且有一些已经在 图论学习条记 1 中涉及到。就是将连通分量变成一个点，在类似连通分量中点之间的边潜伏，只生存连通分量之间的边。
先看题。
CF1000E We Need More Bosses

*2100，似乎没多难。
标题大意：给定一个 nnn 点 mmm 边的连通无向图，须要找到两个点 s,ts,ts,t，使得 sss 到 ttt 必须要颠末的边最多，纵然 无论怎么走都会颠末 的边最多。
我们很容易发现这东西和边双连通分量扯上了关系，由于边双连通分量的界说是：极大的，此中恣意两个点之间至少有两条不重合的路径的连通子图。
显然，假如 sss 到 ttt 在同一个边双连通分量内，它们必须要颠末的边肯定为 000 条。
从而我们可以得出，sss 到 ttt 之间必须要颠末的边，全部都是桥。
于是不妨想到对边双连通分量缩点。绘图可以得到，必须要颠末的边肯定是 Bridge Tree 上面 sss 和 ttt 处于的边双连通分量（假定为 xxx 和 yyy）之间的路径。
于是标题变成了如许：给定一棵树，须要你求上面的最长路。
这不就是树的直径吗！固然这里大概有一些难写。
也有另一种做法：摆列 lcalcalca 的位置，显然 xxx 和 yyy 肯定是在 lcalcalca 的子结点的差别的子树内里（要否则它们的 lca 就不是 lcalcalca 这个值了），设为 T1T_1T1​ 和 T2T_2T2​。
要使路径长度最长，须要使 xxx 在 T1T_1T1​ 中深度最大的位置，yyy 也在 T2T_2T2​ 中深度最大的位置。
显然一个子树中的深度最大位置可以利用树形 dp来求，是底子中的底子了。
然后要算答案的时间，直接取子结点的子树最大深度 的 最大值和次大值 相加即可。
增补：别的，尚有大概是 lcalcalca 和子树中的一个点，直接利用整个子树深度最大更新即可。
这道题就这么做完了，头脑含量真的不高，*2100 大概是边双连通分量的加成。

1. #include <bits/stdc++.h>
2. using namespace std;
3. int n, m;
4. const int N = 300010;
5. vector<int> v[N];//原图
6. set<int> edge[N];//缩点之后的图
7. int p[N], dfn[N];//下面开始跑边双连通分量
8. int num[N], cnt;
10. int find(int x) {
11.         if (p[x] == x)
12.                 return x;
13.         return p[x] = find(p[x]);
14. }
16. void tarjan(int u, int pre) {
17.         dfn[u] = ++cnt, num[cnt] = u;
18.         p[dfn[u]] = dfn[u];
19.         for (auto i : v[u]) {
20.                 if (!dfn[i])
21.                         tarjan(i, u), p[dfn[u]] = min(p[dfn[u]], p[dfn[i]]);
22.                 else if (i != pre)
23.                         p[dfn[u]] = min(p[dfn[u]], dfn[i]);
24.                 else
25.                         pre = 0;
26.         }
27. }
28. //---到上面全是板子
29. int dp[N], dep[N];//准备树形dp
30. //dp[u]表示u的子树内的最大深度
31. int ans = 0;//答案
33. void dfs(int u, int pre) {
34.         dep[u] = dep[pre] + 1;//先更新自己的深度
35.         dp[u] = dep[u];//自己的子树显然包含自己
36.         int mx = 0, sc = 0;//记录最大值和次大值
37.         for (auto i : edge[u]) {
38.                 if (i == pre)
39.                         continue;//这里的树是无根树，所以需要判断
40.                 dfs(i, u);//递归
41.                 dp[u] = max(dp[u], dp[i]);//先更新自己的dp值
42.                 if (dp[i] >= mx)//更新最大值和最小值
43.                         sc = mx, mx = dp[i];
44.                 else if (dp[i] >= sc)
45.                         sc = dp[i];
46.         }
47. //顺便更新答案
48.         ans = max(ans, sc + mx - 2 * dep[u]);//情况1：s 和 t 在两个不同的子结点的子树内
49. //注意还要减去自己深度的两倍
50.         ans = max(ans, dp[u] - dep[u]);//情况2：s 和 t 有一个是自己，另一个是自己的后代
51. }
53. int main() {
54.         cin >> n >> m;
55.         for (int i = 1; i <= m; i++) {
56.                 int x, y;
57.                 cin >> x >> y;
58.                 v[x].push_back(y);
59.                 v[y].push_back(x);
60.         }
61.         tarjan(1, 0);
62.         int rt = 0;//随便选一个根
63.         for (int i = 1; i <= n; i++)
64.                 for (auto j : v[i])
65.                         if (find(dfn[i]) != find(dfn[j])) {//只保留边双连通分量之间的边
66.                                 edge[find(dfn[i])].insert(find(dfn[j]));
67.                                 edge[find(dfn[j])].insert(find(dfn[i]));
68. //注意这里的 i 和 j 都要套上一层 dfn[]，因为 find 是使用的深搜树上编号
69. //find 返回的也是树上编号，但这里无关紧要，所以不需要使用 num 转换。我们关心的是树的结构
70.                                 rt = find(dfn[i]);//记录根
71.                         }
72.         if (rt == 0) {//注意，如果整个图是一个边双连通分量，则这里的 rt 为 0，如果搜索可能会出现问题
73.                 cout << "0";//显然当整个图是边双连通分量的时候没有必须经过的边
74.                 return 0;
75.         }
76.         dfs(rt, 0);//树形dp
77.         cout << ans << endl;
78.         return 0;
79. }

复制代码

CF652E Pursuit For Artifacts

结论题。
不难注意到一件变乱：一个环上面假如有一条边权为 111 的边，则环上面全部的点肯定都可以存在有一条 111 的路径。
环你想到了什么？没错，边双连通分量。
思量证明更加高级的结论：假如一个边双连通分量内里有至少一条边权为 111 的边，则边双连通分量内里全部的点肯定都可以存在一条 111 的路径。
取边双内恣意一条边权为 111 的边，设其两端为 x,yx,yx,y。
我们可以将边双连通分量看成环套环的情势。
先找到同时包罗 x,yx,yx,y 的环。根据边双连通分量恣意两个点都有两条无重复的路径，肯定存在这个环。
将这个环设为1 级环。

将 1 级环缩点，然后再找到一个更大的环，完全包罗这个环：

称为二级环。
以此类推。
如许子，恣意边双连通分量的点，都可以通过环上穿梭的情势颠末这条边权为 111 的边。结论得证。

---

但是假如两个点不在同一个边双连通分量中呢？
不妨先缩点。
这设两个点地点的边双编号为 u,vu,vu,v。
则显然可以直接判断 u→vu \to vu→v 的路径中的全部边双连通分量和桥内里的边有没有边权为 111 的边即可。
由于只有一次扣问，复杂度为 O(n)O(n)O(n)。

---

下面开始讲强连通分量缩点。
强连通分量缩点之后会形成 SCCDAGSCC DAGSCCDAG，也就是一个有向无环图。
有向无环图之后标题就可以变得简朴了：可以变成 DAG 上 DP，也可以考其他内容。
提供一个自己总结的，一样平常性的解题方式：缩点之后，思考此时scc的意义。再思考此时答案有什么意义，怎么求出来。
还是从前讲过了，直接看题吧。
P3627 [APIO2009] 劫掠操持

题面已经讲得富足清楚。
起首这是一个有向图，而且须要注意，他可以颠末同一起口或蹊径恣意多次。
以是可以得出：同一个强连通分量的点可以任意走。
于是这个劫匪可以先把自己的强连通分量内里的点全都给抢了，然后再思量抢其他强连通分量内里的点。

---

可以摆列止境 TTT，然后思量从出发点 SSS 到止境 TTT 最多可以抢多少。
我们发现一个究竟：当这个劫匪到达了一个强连通分量的时间，可以把内里全部的东西都给抢了。纵然这个强连通分量不是 SSS 一开始的强连通分量。

详细地，可以这么走：

于是得到一个很好玩的变乱：这时间就可以利用点权，SCC DAG 上面的点权就是强连通分量内里全部点的点权和。
于是就转变成了喜闻乐见的 DAG DP 经典标题，如许摆列 TTT 的时间可以直接查表。

---

P3119 [USACO15JAN] Grass Cownoisseur G

显然假如不走反边，从 111 开始，最多也只能走完自己强连通分量的点。
于是得到结论：当到达了一个新的强连通分量，这个强连通分量内里全部的点都可以被走到。
以是可以接纳赋值点权的做法：每一个强连通分量缩点之后的点权都是其内部的点的数目。
但是假如要走反边的话，这就有一点难办啊……
实验利用通例套路：直接摆列反边到底是哪一条。
由于这个时间答案只和强连通分量有关，以是设 这条反边的两端 属于的强连通分量 分别是 u,vu,vu,v，并设 111 属于的强连通分量是 www。

这里就不妨设存在 w→uw \to uw→u 和 v→wv \to wv→w 的路径，而 (u,v)(u,v)(u,v) 这条边的方向并不告急。
调转过来之后就变成了如许：

发现，这个时间，可以从 w→u→v→ww \to u \to v \to ww→u→v→w！也就是构成了一条正当的路径！
这时间，我们须要盘算图中的路径（不包罗 u→vu \to vu→v 的一条边，也就是 w→uw \to uw→u 和 v→wv \to wv→w 这两条路径）构成的贡献。
设 dp1idp1_idp1i​ 表现从 www 走到 iii 的一起上途径的最大点权和，不包罗 www 自己。正向跑 dijkstra 大概是拓扑排序都可以。
设 dp2idp2_idp2i​ 表现从 iii 走到 www 的一起上途径的最大点权和，不包罗 www 自己。可以直接建反向图，然后跑 dijkstra 大概是拓扑排序就可以了。
对于 u→vu \to vu→v 的这一条边，答案就是 dp1u+dp2vdp1_u+dp2_vdp1u​+dp2v​。直接预处理惩罚出 dp1,dp2dp1,dp2dp1,dp2 然后就可以直接获取答案。

---