割点与割边
割点的求解方法
割点详解
板题： https://www.luogu.com.cn/problem/P3388 第1题 割点 查看测评数据信息
给出一个n个点，m条边的无向图，求图的割点。
输入格式
第一行输入两个正整数 n,m。
下面m行每行输入两个正整数x,y表示x到y有一条边。
对于全部数据，1≤n≤2×1e4，1≤m≤1×1e5。
点的编号均大于0小于等于n。
输出格式
第一行输出割点个数。
第二行按照节点编号从小到大输出节点，用空格隔开。
输入/输出例子1
输入：
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
输出：
1
5
样例解释
无
#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int n, m, u1, v1, dfn[N], low[N], idx=0, ans=0, root=0;
bool cut[N];
vector<int> a[N];
void dfs(int u, int fa)
{
dfn[u]=low[u]=++idx;
int child=0;
for (int i=0; i<a[u].size(); i++)
{
int v=a[u][i];
if (!dfn[v])
{
child++;
dfs(v, u);
low[u]=min(low[u], low[v]);
if (low[v]>=dfn[u] && u!=root) cut[u]=1;
}
else
{
low[u]=min(low[u], dfn[v]); //*
}
}
if (u==root && child>=2) cut[root]=1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=1; i<=m; i++)
{
scanf("%d%d", &u1, &v1);
a[u1].push_back(v1);
a[v1].push_back(u1);
}
for (int i=1; i<=n; i++)
if (!dfn[i])
{
root=i;
dfs(i, 0);
}
for (int i=1; i<=n; i++)
if (cut[i]) ans++;
printf("%d\n", ans);
for (int i=1; i<=n; i++)
if (cut[i]) printf("%d ", i);
return 0;
}
dfn[i] 表示 进入i节点时的时刻
low[i] 表示 以i节点往上走能够到达的时刻最小值
cut[i] 表示 第i个点是否为割点
然后不断dfs，更新low，时间戳比自身小才更新low值
判断割点条件：
1. low[v]>=dfn[u] 且 u!=1
（不可能走到u上面）
要特判根节点
2.根节点儿子>=2
#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int n, m, u1, v1, dfn[N], low[N], idx=0, ans=0, root=0;
bool cut[N];
vector<int> a[N];
void dfs(int u, int fa)
{
dfn[u]=low[u]=++idx; //更新时间戳，最远跳到的时间戳初始化为自身
int child=0; //该节点孩子数量
for (int i=0; i<a[u].size(); i++)
{
int v=a[u][i];
if (!dfn[v]) //没有被访问过，确保了等下修改的low值是比自身时间戳要小的
{
child++;
dfs(v, u);
//注意，这里要先往下dfs，之后才能更新值
//这样才能让下面的语句生效，从儿子的low值反过来更新父亲的low值
//由于儿子能走到的最远距离（儿子多走了一段 u->v），父亲肯定也能走到
low[u]=min(low[u], low[v]);
//解释1
if (low[v]>=dfn[u] && u!=root) cut[u]=1;
}
else
{
//解释2
low[u]=min(low[u], dfn[v]);
}
}
//解释3
if (u==root && child>=2) cut[root]=1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=1; i<=m; i++)
{
scanf("%d%d", &u1, &v1);
a[u1].push_back(v1);
a[v1].push_back(u1);
}
//此题没规定一定联通，所以分别以每个点为根来找
for (int i=1; i<=n; i++)
if (!dfn[i])
{
root=i;
dfs(i, 0);
}
for (int i=1; i<=n; i++)
if (cut[i]) ans++;
printf("%d\n", ans);
for (int i=1; i<=n; i++)
if (cut[i]) printf("%d ", i);
return 0;
}
解释1+解释3：
low[v]>=dfn[u]，即儿子走到的最远距离不超过父亲，那么这个时候隔断父亲，儿子也会跟着断。
反之亦然，如果儿子走过的最远距离超过父亲，就算隔断父亲，儿子还是能走过去
这种情况要注意是不是根节点
假设此时u为根节点，他的儿子是v，v的儿子有很多很多
此时儿子v最远跳到u，那么就满足了“low[v]>=dfn[u]”
那么u被认为是割点，但其实删去u，图还是连通的！
所以要此时要特判u不为根节点，此方法才生效。
那如何求x为根节点的情况？只需要看x的儿子是否>=2即可
也就是解释3
解释2：
如果按照“low[u]=min(low[u], low[v])"来执行，4号点和5号点的low值都为1，那么这样判断下3号节点将不会是割点，事实上3号节点是一个割点。
所以要按照“low[u]=min(low[u], dfn[v])"来执行，确保3号节点能正常判断
例题：
https://www.luogu.com.cn/problem/P5058
第2题 嗅探器 查看测评数据信息某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络。蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息。
但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。
现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？
输入格式
输入文件的第一行一个整数 n，表示蓝军网络中服务器的数目。
接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数i,j表示编号为i和编号为j的两台服务器间存在双向连接。
服务器的编号从1开始，一行两个0表示网络的拓扑结构描述结束，再接下来是两个整数a,b分别表示两个中心服务器的编号。
1≤n≤2×1e5，边数不超过 5×1e5
输出格式
输出满足条件的服务器编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。
输入/输出例子1
输入：
5
2 1
2 5
1 4
5 3
2 3
5 1
0 0
4 2
输出：
1
样例解释
无
割点好题。
标签：连通性,int,无向,割点,dfn,low,root,节点 From： https://www.cnblogs.com/didiao233/p/18302884