【下海捕鱼】割顶与桥的求解

72 阅读 0 评论 48 点赞

我是靠谱客的博主留胡子鸭子，这篇文章主要介绍【下海捕鱼】割顶与桥的求解，现在分享给大家，希望可以做个参考。

Description

给出一个n个点（编号1..n），m条边的无向图，求图的割顶和桥。

Input Data

包含多组测试数据，每组数据格式如下：
第一行输入n,m（n,m <= 100000;
下面m行每行输入u,v表示u和v之间有边。
最后一行是n=m=0，表示数据结束。

Output Data

对于每组数据，输出：
第一行输出割顶的个数和桥的条数。
若割顶数不为0，则第二行开始按照节点编号从小到大输出各个割顶，一个一行。

Input Sample

6 7
1 2
1 3
2 5
3 5
5 6
4 5
1 4
5 6
4 1
4 5
5 1
1 2
1 3
2 3
0 0

Output Sample

1 1
5
1 0
1
——————————————————分割の线——————————————————

分析

也分析不出个所以然来。因为是道模板题，就直接介绍几个概念，然后上代码；
预备知识
割顶：Cut Vertex，对于无向图G，如果删除某个顶点u后，连通分量数目增加，则u便是图G的关节点（Articulation Vertex）或割顶。
桥：Bridge，如果删除某条边，G就非连通了，这条边就称之为桥。

概念1 时间戳
某一点的时间戳即是该点在DFS中被访问的顺序，如果v的时间戳小于u的时间戳则v是u的祖先 (因为祖先先访问嘛)。
用全局变量dfs_clock表示“当前时刻”，定义pre[u]表示u的顺序（或称为到达u点时的时刻）,伪代码如下：

复制代码

1
2
3
memset(pre,0,sizeof(pre));
dfs_clock=0;
pre[u]=++dfs_clock;

概念2 树边和反向边
树边：在dfs森林中被遍历的边；
反向边：第一次处理后，子孙指向祖先的边。可认为是除去树边外的所有边。

dfs的森林

概念3 割顶特性
定理1->容易看出，割顶至少要与两点相连，所以若为根节点，需要有两个及以上的孩子；若不为根节点，则需要至少一个孩子结点
用low[u]表示u及其子孙所能到达的最早祖先；
定理2->容易想到的是若有一个点，它的子孙所能到达的最早的点，大于等于自己，则此点是割顶（动手画一画，想一想是为什么）。用数组表示为

复制代码

1
low[v]>=pre[u]

之后可以通过dfs求low[u]的值，顺道完成求割顶和桥的操作。
代码如下

复制代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int>g[100010];
int dfs_clock;
int cnt_bridge,cnt_cut;
int low[100010],is_cut[100100];
int pre[100010],post[100010];
void pre_visit(int u)
{
pre[u]=++dfs_clock;
}
void post_visit(int u)
{
post[u]=++dfs_clock;
}
int dfs(int u,int fa)//u在DFS数中的父亲结点是fa
{
int lowu=pre[u]=++dfs_clock;
int child=0;//子结点数目
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!pre[v])//访问过v
{
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);//通过后代的lowv更新lowu值
if(lowv>=pre[u]) is_cut[u]=1;//如果v能到达的最早的祖先小于等于它的祖先u ，则u是割点
if(low[v]>pre[u]) cnt_bridge++;//如果儿子v只能到达u，则(u,v)是一座桥，删去后连通分量+1
}
else if(pre[v]<pre[u]&&v!=fa)//通过反向边更新lowu的值
{
lowu=min(lowu,pre[v]);
}
}
if(fa<0&&child==1) is_cut[u]=0;//只有一个子结点的根结点不是割顶
low[u]=lowu;//更新low[u]的值；
return lowu;//返回值，对应父亲结点的lowv
}
int main()
{
int n,m;
cin>>n>>m;
memset(is_cut,0,sizeof(is_cut));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)
g[i].clear();
cnt_bridge=0;
cnt_cut=0,dfs_clock=0;//每次的初始化
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!pre[i])
dfs(i,-1);
for(int i=1;i<=n;i++)
if(is_cut[i])cnt_cut++;
printf("%dn",cnt_cut);
for(int i=1;i<=n;i++)
if(is_cut[i]) printf("%d ",i);//输出割顶
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int>g[100010];
int dfs_clock;
int cnt_bridge,cnt_cut;
int low[100010],is_cut[100100];
int pre[100010],post[100010];
void pre_visit(int u)
{
pre[u]=++dfs_clock;
}
void post_visit(int u)
{
post[u]=++dfs_clock;
}
int dfs(int u,int fa)//u在DFS数中的父亲结点是fa
{
int lowu=pre[u]=++dfs_clock;
int child=0;//子结点数目
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!pre[v])//访问过v
{
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);//通过后代的lowv更新lowu值
if(lowv>=pre[u]) is_cut[u]=1;//如果v能到达的最早的祖先小于等于它的祖先u ，则u是割点
if(low[v]>pre[u]) cnt_bridge++;//如果儿子v只能到达u，则(u,v)是一座桥，删去后连通分量+1
}
else if(pre[v]<pre[u]&&v!=fa)//通过反向边更新lowu的值
{
lowu=min(lowu,pre[v]);
}
}
if(fa<0&&child==1) is_cut[u]=0;//只有一个子结点的根结点不是割顶
low[u]=lowu;//更新low[u]的值；
return lowu;//返回值，对应父亲结点的lowv
}
int main()
{
int n,m;
cin>>n>>m;
memset(is_cut,0,sizeof(is_cut));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)
g[i].clear();
cnt_bridge=0;
cnt_cut=0,dfs_clock=0;//每次的初始化
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!pre[i])
dfs(i,-1);
for(int i=1;i<=n;i++)
if(is_cut[i])cnt_cut++;
printf("%dn",cnt_cut);
for(int i=1;i<=n;i++)
if(is_cut[i]) printf("%d ",i);//输出割顶
return 0;
}