[HAOI2010] 软件安装
一眼缩点然后树上背包。
注意一些写法上的问题和一些细节：
- 强连通分量要写
in_stack。 - 缩点后可能是一个森林，要连边到虚根。
- 如果一个环缩成一个点，也要连到虚根。
- 没跑 tarjan 前也要把点连到虚根。
P3854 [TJOI2008] 通讯网破坏
先点双，把割点单拎出来建成一个点，其余的建成一个点，然后就是一个树形结构。
如果 S 和 T 在一个点双内，那么肯定无法断开；
如果 M 是一个割点，同时 M 在 S 和 T 之间路径上，那么就可以断开，否则不行。
首先可以树剖，其次可以考虑树上一点在两点路径上的充要条件：
\[dis(S, M) + dis(M, T) = dis(S, T)
\]
这个可以用 lca + dep 维护。
或者我们可以跑一个圆方树，其本质就是一颗连通性与原图相同的树，所以之前的操作也可以在圆方树上进行。
注意，建圆方树时，不用对根进行特判，跳栈推荐写法：
while (true) {int x = st.top(); st.pop();edge[tot].push_back(x);edge[x].push_back(tot);if (x == v) break;
}
P1407 [国家集训队] 稳定婚姻
如果一对男女不稳定，那么定然是他们在一个环上面，然后每个人轮换到下家。
同时，这个环上的边，是婚姻-初恋轮换出现的。
考虑如果是双向边的话，就没法出来边的轮换，所以我们建立单向边，同时，因为轮换的缘故，其中如果婚姻关系是男->女，那么初恋关系就要是女->男。
建出来这个图后，tarjan 判环（强连通分量），打上 belong 就行。
注意，要对每个点跑一边 tarjan。
for (int i = 1;i <= n;i++) {if (!dfn[i]) tarjan(i);
}