割点、割边整理
little_prince · · 个人记录
因为先学习的强连通分量，所以在这里就不赘述dfn和low数组啦。不过在这里可以再一次感受到这两个数组的强大。
一.割点
首先通过DFS把无向图定向成有向图，定义每个顶点两个参数，即dfn和low数组。
（还是再重复一遍吧）
1.dfn[u]记录顶点u访问的先后顺序。
2.low[u]（lowlink[u]也可）表示沿u出发的有向轨能够到达的点v中，dfn[v]值的最小值（若经过返祖边就停止），初始值为dfn[u]。
判断割点：
1.u = root（这个root指的是从每一个连通子图开始tarjan的第一个点），则判断它是否有至少2个儿子，如果有，那么它是割点，反之不是。（增加的参数root_son即是记录根节点儿子数）
2.对于其他顶点u，如果其儿子v的参数low[v] >= dfn[u],则u为能够断开该儿子及该儿子的子树的割点。这里是我的个人理解，但我觉得这很重要，因为在后面的题目涉及指定两点不连通时这是理解的核心。
二.割边
判断割边：
比判断割点更简单。只需要改成low[v] > dfn[u]，则u->v为割边即可。
注意： 割点和割边没有直接关系，说法“两个割点之间的边必为割边”“割边两端点为割点”都是错误的。
三.例题
记一个好的例题：嗅探器
一句话题意:求一个编号最小的割点，使得题目指定的a，b点不连通。
本题我来详细阐述一下思考过程。
首先的想法是把原图中所有的割点求出来。这里就有一个疑问，以哪个点为根节点用DFS把无向图转成有向图呢？先暂时搁置。
然后想，如果说求出的割点使a，b不连通，那么把这个点割掉，a，b之间就没有一条路径能够到达。那么反过来，所有a能够到b（或b到a）的路径中必然含有此割点，否则把该割点割掉，却还有ab互通的路径，就没有达到目的了。
因此，我们要求的割点必然在a，b的路径上。如果a，b路径上无割点，说明a，b处在一个点双连通分量中（一个割掉任意一点所有点仍连通的子图），那么输出无解。
因此，我们可以简便的以a（起点）为根节点通过DFS建立有向图，然后记录下每个点的父节点。注意，这里是DFS建立的有向图，不是单纯的一颗树！只是我们把返祖边抛开不看是一棵从根节点向下的有向树！
由以上分析知道，所求割点一定在b通过树枝边（相邻父子节点）回溯到a的路径上。大致思路清晰了。
接着，说一个我查错很久才查出来的一个问题。我们能不能在开始tarjan的时候就通过Mark数组标记顶点是否为割点，然后在b回溯到a时候直接判断是否为割点呀？
这是错的，答案会判多！
仔细思考割点的判定方式可知（也就是我一开始提到的），判断的割点割的不一定是所要求的两部分的分割。我们只是说真正能分割a，b的割点一定在a，b路径上，没有说a，b路径上的割点一定能割开a，b。这是核心！
因此我们选择在从b到a回溯的时候，再来判断是否能够割开。
好啦，细节说这么多，上代码：
#include<bits/stdc++.h>
using namespace std;
const int VN = 2*1e5 + 17,EN = 1e6 + 17;
inline int read(){
int f=1,r=0;char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){r=r*10+c-'0';c=getchar();}
return f*r;
}
struct node{
int to,next;
}edge[EN*2];
int head[VN],edge_tot;
void add(int u,int v){
edge[++edge_tot].to = v;
edge[edge_tot].next = head[u];
head[u] = edge_tot;
}
int N,X,Y,x,y,Mark[VN],root;
int dfn[VN],fa[VN],low[VN],num;
void tarjan(int x){
dfn[x] = low[x] = ++num;
for(int i = head[x];i;i = edge[i].next)
{
int y = edge[i].to;
if(y == fa[x]) continue;
if(!dfn[y])
{
fa[y] = x;
tarjan(y);
low[x] = min(low[x],low[y]);
if(dfn[x] <= low[y] && dfn[y] <= dfn[Y])
{
if(!Mark[x]) Mark[x] = 1;
}
}
else low[x] = min(low[x],dfn[y]);
}
}
int ans = 0x3f3f3f3f;
void dfs(int x){
if(x == X) return;
if(Mark[fa[x]] && fa[x] != X && fa[x] < ans) ans = fa[x];
dfs(fa[x]);
}
int main(){
N = read();
while(1){
x = read();y = read();
if(x == 0 && y == 0) break;
add(x,y);add(y,x);
}
X = read();Y = read();
tarjan(X);
/*for(int i = 1;i <= N; i++)
if(!dfn[i]){
root_son = 0;root = i;
tarjan(i);
if(root_son == 1) Mark[root] = 0;
}*/
dfs(Y);
if(ans == 0x3f3f3f3f){cout<<"No solution"<<endl;return 0;}
cerr<<"ans = ";cout<<ans<<endl;
return 0;
}
/*
30
6 23
30 25
26 23
26 8
18 3
30 11
23 8
12 24
16 25
19 20
23 29
26 29
11 22
23 4
6 24
28 29
4 10
19 9
27 28
9 20
21 23
13 22
24 14
22 30
5 23
29 27
14 28
10 26
16 19
21 26
25 17
1 14
27 23
10 8
3 19
8 21
8 27
27 5
29 12
7 25
11 17
3 23
8 14
3 26
14 3
30 19
18 14
3 28
22 17
28 4
21 5
25 3
21 24
9 3
13 3
10 27
16 9
24 23
9 13
10 24
29 21
30 13
11 3
13 20
29 10
12 5
21 27
3 4
10 6
12 3
11 25
26 27
6 18
3 17
13 19
25 9
16 22
21 10
25 13
27 4
20 16
28 26
30 16
7 19
7 3
23 28
18 23
10 23
8 4
5 18
5 28
30 7
24 5
3 8
16 7
9 22
18 8
28 18
3 10
24 8
18 10
18 29
21 4
12 18
28 12
26 4
20 30
10 14
4 18
6 21
21 18
12 27
6 29
6 14
5 26
28 21
7 13
8 28
3 20
9 30
5 4
13 16
11 13
20 17
12 8
3 21
11 9
2 14
28 24
26 24
7 20
6 28
27 6
27 24
14 21
15 1
21 12
5 14
12 23
25 19
3 29
12 10
26 18
4 6
24 4
3 30
19 22
5 10
12 6
2 1
4 14
22 3
17 13
15 2
20 22
17 7
29 8
6 8
8 5
3 6
17 30
19 11
7 11
27 14
26 6
18 27
12 14
16 3
10 28
16 11
15 14
20 11
14 26
29 14
20 25
16 17
3 24
22 7
25 22
9 17
29 5
12 4
19 17
6 5
29 24
9 7
27 3
4 29
12 26
3 5
24 18
23 14
0 0
2 1
No solution
*/第二个题是一道结论题，不过也很重要！ 同时关于tarjan算法有了一定经验，其实真正写求割边的算法的机会貌似不多，更多的是求强连通分量（有向图），割点和块儿（无向图）写的多一些。
https://www.luogu.com.cn/problem/P2860
拿到这个题很明显是要我们把原图构造成一整个边双连通分量。那么我们去枚举边构造吗？显然不可能，这是很笨的办法，而且题目只求新添加的边的数量。
那么首先，我们需要把原图中已有的双连通分量缩点，缩点完后原图割边连接的连通块一定构成一棵树。（本题数据中原图没有单独不与任何连通的点，不过以后写时还要仔细看题条件） 对于这棵树（都是无向边），显然我们是要把入度为1的点都连起来。怎么连呢？
猜想：每连一条边，就选择树中的两个节点，将它们连起来，于是最少的增加的边的数目就是（叶子节点个数+1）/2。
其实很好证明，看下面的图意会一下两种连法的不同，然后联想一下最近公共祖先，就会发现我们在形成的一棵树中，每次完全可以找到一种连法，使得原来的两个叶子节点连在一起不会产生新的叶子节点。
附上代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2*1e5 + 7;
inline int read(){
int f=1,r=0;char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){r=r*10+c-'0';c=getchar();}
return f*r;
}
int N,M,A,B;
struct node{
int from,to,next;
}edge[MAXN];
int head[MAXN],edge_tot;
void add(int u,int v){
edge[++edge_tot].to = v;
edge[edge_tot].from = u;
edge[edge_tot].next = head[u];
head[u] = edge_tot;
}
int fa[MAXN],dfn[MAXN],T[MAXN],low[MAXN],st[MAXN],top,num,cnt;
void tarjan(int x){
dfn[x] = low[x] = ++num;
st[++top] = x;
for(int i = head[x];i;i = edge[i].next)
{
int y = edge[i].to;
if(y == fa[x]) continue;
if(!dfn[y])
{
fa[y] = x;
tarjan(y);
low[x] = min(low[x],low[y]);
}
else if(!T[y]) low[x] = min(low[x],dfn[y]);
}
if(dfn[x] == low[x])
{
T[x] = ++cnt;
while(st[top] != x)
{
T[st[top]] = cnt;
top--;
}
top--;
}
}
int rd[MAXN],cd[MAXN];
bool cmp(node a,node b){
if(a.from == b.from) return a.to < b.to;
return a.from < b.from;
}
void solve(){
//for(int i = 1;i <= N; i++)
//printf("T[%d] = %d\n",i,T[i]);
sort(edge + 1,edge + edge_tot + 1,cmp);
for(int i = 1;i <= edge_tot; i++)
{
if(i!=1&&edge[i].from == edge[i-1].from && edge[i].to == edge[i-1].to) continue;
int x = edge[i].from,y = edge[i].to;
if(T[x] != T[y]) rd[T[y]]++;
}
int ans = 0;
for(int i = 1;i <= cnt; i++)
{
if(rd[i] == 1) ans++;
}
printf("%d\n",(ans + 1)/2);
}
int main(){
N = read();M = read();
for(int i = 1;i <= M; i++)
{
A = read();B = read();
add(A,B);add(B,A);
}
for(int i = 1;i <= N; i++)
if(!dfn[i]) tarjan(i);
solve();
return 0;
}