part 1：离线求 \(lca\)
将走过的点且未回溯的标记为 \(1\)，已回溯的标记为 \(2\)，未访问标记为 \(0\)
把对于一点 \(x\) 的询问 \(y\) 存进相应的 \(vector\)，当回溯时判断如果询问的点标记为 \(2\)，则 \(lca\) 为询问的点 \(y\) 到根的路径上最早标记为 \(1\) 的点
但直接找复杂度不对
我们用并查集优化，当一个节点标记为 \(2\)，即回溯时把它所在集合与它父节点所在集合合并
因为合并时父节点标记仍为 \(1\)，且集合只有它自己，相当于每个回溯了的节点有指针指向它的父节点
用并查集的路径压缩，即可快速找到那个为 \(1\) 的点，就是 \(find(y)\)
part 2：求割边
定义
割边/桥：对于一个无向连通图，若删去这条边图后不连通，则这条边为割边
树边：对无向图进行 \(dfs\)，则经过的边为树边，未经过的边为非树边，且在无向图中一定是返祖边
\(dfn[x]\)：\(x\) 在树上被遍历到的时间戳
\(low[x]\)：从 \(x\) 及其子树沿一条返祖边能到的 \(dfn\) 最小的值
性质
若一条边 \((x,y)\) 为割边，\(x\) 为 \(y\) 父节点，则 \(low[y]>dfn[x]\)
很好理解，\(y\) 通过非树边不能到 \(x\) 及上方的的点，删掉边后 \(x\) 与 \(y\) 一定不连通
所以桥一定是树边，且不被包含于任何一个简单环中
代码：
注意 \((x,y)\) 有重边的情况，只有一条算树边，\(dfn[fa]\) 能更新 \(low[x]\)，都不能算割边
用成对变换的技巧，标记哪条边是从 \(fa\) 过来的边，其它边都正常处理
inline void tarjan(int x, int faedg) // 求割边
{
dfn[x] = low[x] = ++cnt;
for(reg int i = 0; i < (int)edge[x].size(); ++i)
if(!dfn[edge[x][i].fi])
{
tarjan(edge[x][i].fi, edge[x][i].se);
low[x] = min(low[x], low[edge[x][i].fi]);
if(low[edge[x][i].fi] > dfn[x]) book[edge[x][i].se] = book[edge[x][i].se ^ 1] = 1;
}
else if(edge[x][i].se != (faedg ^ 1)) low[x] = min(low[x], dfn[edge[x][i].fi]);
}
part 3：求割点
定义：
割点：删除这个点以及它所连的边后，无向连通图不连通的点
性质：
若 \(x\) 为割点且不是根，即 \(x\) 在搜索树上的一个子节点 \(y\)，\(low[y] \ge dfn[x]\)
但特别的，若 \(x\) 为根，则搜索树上要至少两个 \(y\) 满足条件，即 \(x\) 至少有两个孩子为割点
判定时因为是 \(\ge\)，不用考虑是否为父节点/重边，从 \(x\) 出发到达的所有点 \(dfn\) 都能更新 \(low[x]\)
代码：
inline void dfs(int x, int fa)
{
int son = 0; // 子节点数
dfn[x] = low[x] = ++cnt;
for(reg int i = 0; i < (int)edge[x].size(); ++i)
if(!dfn[edge[x][i]]) // 未访问过，沿树边
{
dfs(edge[x][i], x), ++son;
low[x] = min(low[x], low[edge[x][i]]);
if(low[edge[x][i]] >= dfn[x] && fa) cut[x] = 1;
}
else low[x] = min(low[x], dfn[edge[x][i]]); // 访问过，返祖边
if(fa == 0 && son > 1) cut[x] = 1; // 特判根
}
part 4：求边双连通分量
定义：
\(e-DCC\)：无向图中一张极大的不含割边的子图
极大：指没有另一个 \(e-DCC\) 包含它
性质：
-
割边不在任何边双中，其它的边只在一个边双中
-
边双中，任意边都至少包含于一个简单环中
求法：
这里由于割边划分了不同边双，去掉割边后每个连通块就是一个边双
先求边双，最后再对未经过的点 \(dfs\)，不经过割边即可
inline void tarjan(int x, int faedg) // 求割边
{
dfn[x] = low[x] = ++cnt;
for(reg int i = 0; i < (int)edge[x].size(); ++i)
if(!dfn[edge[x][i].fi])
{
tarjan(edge[x][i].fi, edge[x][i].se);
low[x] = min(low[x], low[edge[x][i].fi]);
if(low[edge[x][i].fi] > dfn[x]) book[edge[x][i].se] = book[edge[x][i].se ^ 1] = 1;
}
else if(edge[x][i].se != (faedg ^ 1)) low[x] = min(low[x], dfn[edge[x][i].fi]);
}
inline void dfs(int x, int fa)
{
vis[x] = 1, edcc[sum].push_back(x);
for(reg int i = 0; i < (int)edge[x].size(); ++i)
if(!vis[edge[x][i].fi] && !book[edge[x][i].se]) dfs(edge[x][i].fi, x);
}
缩点：
把每个 \(e-DCC\) 看作一个点，割边为连接它们的边
得到树/森林
把一张图连到每两点间都有一条边不重复路径的最小边数：
\[\left\lceil\ \frac{\text{缩点后度为 1 的点数}}{2}\right\rceil \]part 5：求点双连通分量
定义：
\(v-DCC\)：无向图中一张极大的在这个子图中不含割点的子图
极大：指没有另一个 \(v-DCC\) 包含它
性质：
-
孤立点/两个点单独构成一个点双
-
割点会属于多个点双，其它点只在一个点双中出现
-
点双中，任意两点都至少同时包含于一个简单环中，点数 \(>2\) 时任意两点间都有至少2条点不重复路径，且在同一点双中任意两点 \(x,y\) 都能找到经过点双中另一点 \(z\) 的点不重复路径
-
两个点双至多有一个公共点——割点
求法：
由于割点会在多个点双中，因此我们要用栈来维护哪些点正在遍历还未回溯
当搜到割点时，把栈弹出直到割点的那个子节点被弹出，割点不能被弹出，因为它可能与其它节点组成点双
对于根，它可以看作割点，归到它子节点的点双中
inline void dfs(int x, int fa)
{
dfn[x] = low[x] = ++cnt, stk[++top] = x;
int child = 0;
for(reg int i = 0; i < (int)edge[x].size(); ++i)
if(!dfn[edge[x][i]])
{
dfs(edge[x][i], x);
low[x] = min(low[x], low[edge[x][i]]);
if(low[edge[x][i]] >= dfn[x]) // x为割点或根
{
vdcc[++sum].push_back(x), ++child;
while(top && stk[top + 1] != edge[x][i]) vdcc[sum].push_back(stk[top--]);
}
}
else low[x] = min(low[x], dfn[edge[x][i]]);
if(fa == 0 && !child) vdcc[++sum].push_back(x); // 特判孤立点
}
缩点：
原图的点为圆点，每个点双看作一个方点，方点向这个点双中含有的点连边
得到一棵树，为圆方树
树上的方点和圆点交错，一个圆点为原图中割点，当且仅当它在圆方树上的度数 \(>1\)
这样我们就方便进行树形 DP 了
题意为图上割掉一点后，剩下的点都能到达一个有出口的点，求有出口的点的最少数量及安排方案数
想到割点
在一个 v-dcc 中，割掉一个点后，剩下的点仍能互相到达，不影响连通性
因此把点双缩点，割掉割点后会产生影响
这里分情况讨论
-
如果点双中无割点，则全图无割点，要选 2 个出口互保，防止出口被割，此时随便选 2 个，方案数为 \(\frac{siz\times(siz-1)}{2}\)
-
如果点双中只有一个割点，即这个点双在缩点后得到的树中为叶子节点，防止那个割点被割，在其它地方建出口，方案数为 \(siz-1\)
-
如果点双中有一个以上割点，那无论哪个割点被割都可通过其它割点走到其它点双，不需要建出口
方案数用乘法原理相乘即可
注：不能在 tarjan 内计算答案，因为此时割点没算完，会算错
code:
#include<bits/stdc++.h>
#define reg register
#define pb push_back
using namespace std;
typedef long long ll;
ll m, n, u, v, dfn[1010], low[1010], book[2010], cnt, sum, t, stk[1010], top, ans, res;
vector<ll> edge[1010], vdcc[2010];
inline ll read()
{
reg char ch = getchar(); reg ll x = 0;
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x;
}
inline void dfs(int x, int fa)
{
dfn[x] = low[x] = ++cnt, stk[++top] = x; int child = 0;
for(reg ll i = 0; i < (ll)edge[x].size(); ++i)
{
if(!dfn[edge[x][i]])
{
dfs(edge[x][i], x);
low[x] = min(low[x], low[edge[x][i]]);
if(low[edge[x][i]] >= dfn[x])
{
if(x != 1) book[x] = 1;
++sum, ++child, vdcc[sum].pb(x);
do vdcc[sum].pb(stk[top--]);
while(top && stk[top + 1] != edge[x][i]);
}
}
else if(edge[x][i] != fa) low[x] = min(low[x], dfn[edge[x][i]]);
}
if(x == 1 && child > 1) book[x] = 1;
}
int main()
{
m = read();
while(m)
{
for(reg ll i = 1; i <= n; ++i) edge[i].clear(), dfn[i] = book[i] = low[i] = 0;
for(reg ll i = 1; i <= sum; ++i) vdcc[i].clear();
++t, n = cnt = sum = ans = 0, res = 1;
for(reg ll i = 1; i <= m; ++i)
{
u = read(), v = read(), n = max(n, max(u, v));
edge[u].pb(v), edge[v].pb(u);
}
dfs(1, 0);
for(reg ll i = 1; i <= sum; ++i)
{
ll num = 0;
for(reg ll j = 0; j < vdcc[i].size(); ++j) num += book[vdcc[i][j]];
if(num == 0) ans += 2, res *= vdcc[i].size() * (vdcc[i].size() - 1) / 2;
else if(num == 1) ans += 1, res *= (vdcc[i].size() - 1);
}
printf("Case %lld: %lld %lld\n", t, ans, res);
m = read();
}
return 0;
}
part 6：求强连通分量
定义：
强连通分量(\(SCC\))：有向图中任意两点可以互相到达的子图
性质：
-
环一定是 \(SCC\)，\(SCC\) 中任意两点互相可达
-
每个点只在1个 \(SCC\) 中出现
求法：
考虑搜索树上有哪些可以构成环
将所有搜到的点入栈，若 \(dfn_x=low_x\)，则栈中从 \(x\) 到栈顶的点构成 \(SCC\)
注意判断更新 \(low_x\) 的点暂时不在其它强连通分量中，为了去除横插边
这时 \(dfn_y\) 换成 \(low_y\) 也可以，但是为了保险且不与其它混淆还是写 \(dfn\)
inline void tarjan(int x)
{
dfn[x] = low[x] = ++cnt, stk[++top] = x;
for(int y : edge[x])
if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
else if(!col[y]) low[x] = min(low[x], dfn[y]); // 注意，y不在另一个强连通分量中
if(dfn[x] == low[x])
{
++sum, scc[sum].pb(x), col[x] = sum;
while(top && stk[top] != x) col[stk[top]] = sum, scc[sum].pb(stk[top--]);
--top; // 注意弹出 x
}
}
缩点
把每个 \(SCC\) 看作一点，\(SCC\) 直接互相有连边的仍连边，则得到有向无环图
可以进行拓扑排序/dp 等操作
把一张有向图连成强连通图最少所需边数：缩点后DAG中 \(\min(\)入度为 \(0\) 的点数 \(,\) 出度为 \(0\) 的点数\()\)
例题1：啊哈添柴12368. 杀人游戏
题中的认识关系可看作有向边，建出有向图
首先直观的想法是入度为 0 的点都得验证，否则没法知道，如果有人是杀手那就无了
在认识的一圈人中
-
如果有人是杀手，就找到了
-
如果没有杀手，那全都是平民，可以放心调查，接着知道他们认识的人，传递下去
所以——一个强连通分量中只需调查一个人，其中剩下的人都能知道
一个强连通分量缩为一点，图变为 DAG
知道 DAG 所有入度为 0 的点一定能推全图
但有特殊情况——一定要知道所有入度为 0 的点吗？
样例2 给了特例，一个点在知道剩下所有点后可通过排除法知道
特判一下，如果一个入度为 0 的点连接的点都连接了不止它这一个入度为 0 的点，则可以用排除法，\(ans-1\)
代码：
#include<bits/stdc++.h>
#define pb push_back
#define iter set<int>::iterator
using namespace std;
const int N = 200010;
int n, m, u, v, col[N], deg[N], dfn[N], vis[N], siz[N], ans, num, flag, book, stk[N], top, low[N], cnt, idx;
double pr = 1.0;
vector<int> edge[N]; set<int> chu[N], ru[N];
inline int read()
{
char ch = getchar(); int x = 0;
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x;
}
inline void tarjan(int x)
{
dfn[x] = low[x] = ++cnt, stk[++top] = x;
for(int y : edge[x])
if(!dfn[y]) tarjan(y), low[x] = min(low[y], low[x]);
else if(!col[y]) low[x] = min(low[x], dfn[y]);
if(dfn[x] == low[x])
{
++idx, col[x] = idx, siz[idx] = 1;
while(top && stk[top] != x) col[stk[top]] = idx, ++siz[idx], --top;
--top;
}
}
inline void dfs(int x)
{
vis[x] = num;
for(iter it = chu[x].begin(); it != chu[x].end(); ++it)
if(!vis[*it]) dfs(*it);
}
inline void rebuild()
{
for(int i = 1; i <= n; ++i)
for(int j : edge[i])
if(col[i] != col[j]) chu[col[i]].insert(col[j]), ru[col[j]].insert(col[i]);
for(int i = 1; i <= idx; ++i)
if(!vis[i]) ++num, dfs(i);
for(int i = 1; i <= idx; ++i)
if(ru[i].empty())
{
++ans, flag = 1;
for(iter it = chu[i].begin(); it != chu[i].end(); ++it)
if(ru[*it].size() < 2) {flag = 0; break;}
if(flag && !book && siz[i] == 1) --ans, book = 1;
}
}
int main()
{
n = read(), m = read();
for(int i = 1; i <= m; ++i)
{
u = read(), v = read();
edge[u].pb(v);
}
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i);
rebuild();
// for(int i = 1; i <= ans; ++i) pr *= (double)(n - i) * 1.0 / (n - i + 1);
printf("%.6lf", (double)1.0 - ((double)ans * 1.0 / n));
return 0;
}