割顶&点双连通分量&P3225 [HNOI2012]矿场搭建

终于A了~~

好久没写博客了,我得水一篇……

割顶

什么是割点?

对于无向图GG,如果删除某个点uu后,连通分量数目增加,称uu为图的关节点或割顶。对于连通图,割顶就是删除之后使图不再联通的点。

怎么求?

DFS树

学习求割顶之前要先学习dfs树。

dfs树就是将有向连通图转化为搜索树,节点以dfs序排列。

树上的一些定义:
  • dfndfn:时间戳,结点被访问的次序。(起点为$1 ,每次搜索+1$)

  • lowlow:结点所能到达的最小dfndfn值 。

  • 树边:dfsdfs树上应有的边,又父节点指向子节点 。

  • 返祖边:dfsdfs树上不应有的边,且该边由子辈节点指向父辈节点。(注意这里不一定是父子节点)

  • 横叉边:连接的两个点无父子辈关系。(注意横叉边一定由dfndfn值大的节点指向dfndfn值小的节点,否则它是树边)

  • 图中55节点的lowlow值为55而不是44,是因为横插边(5,6)(5,6)会被忽略,看不懂的话,等到下面讲到处理横叉边的时候再理解即可。

我要引用冯巨佬的一张图,来举例:

006oZqiLly1g0o78oufhyj30hk0kdjui.jpg

学完大法师树之后,我们就可以学习求割顶了

思路

为了方便叙述,我们只讨论连通图。在这样的情况下,大法师森林一定只有一棵树。那么树根是不是割顶呢?不难发现,当且仅当它有两个或更多的子节点时,它才是割顶——无向图只有树边和反向边,不存在跨越两棵子树的边。对于其他点,我们有下面的定理:

定理:在无向联通图G的大法师树中,非根节点u是G的割顶当且仅当u存在一个子节点v,使得v及其所有后代都没有反向边连回u的祖先

可以看下图,很容易看出u是一个割点。

1.jpg

可以看下图,很容易看出u不是一个割点。

2.jpg

综上,很容易看出,若lowvdfnulow_v \ge dfn_u,则满足定理中的条件,uu即为割顶。

如果不知道dfndfnlowlow是什么,就去看看上面的大法师树吧。

如果还是不理解,就多读几遍!

模板code

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
//模板:https://www.luogu.org/problemnew/show/P3388
const……maxn1……
const……maxn2……

struct edge{……}map[maxn2<<1];

int n,m,dfn[maxn1],low[maxn1],tot;bool iscut[maxn1];
int cnt,head[maxn1];

inline int read(){……}

inline void add(int x,int y){……}

void dfs(int x,int fa){//x是当前节点,fa是当前节点的父亲节点。规定树根的父亲节点是0.
int child=0;//当前点的子节点数
dfn[x]=low[x]=++cnt;//时间戳更新
for(int i=head[x];i;i=map[i].next){
int y=map[i].to;
if(!dfn[y]){//如果没有访问过
child++;//子节点数+1
dfs(y,x);//向下走
low[x]=std::min(low[x],low[y]);//更新low值
if(low[y]>=dfn[x]) iscut[x]=true;//如果符合定理,那么x就是割顶
}
else if(y!=fa) low[x]=std::min(low[x],dfn[y]);//如果访问过了,更新low值
}
if(!fa&&child==1) iscut[x]=false;//当且仅当它有两个或更多的子节点时,树根才是割顶
return;
}

int main(){
n=read(),m=read();
for(register int i=1;i<=m;i++){
int x=read(),y=read();
add(x,y),add(y,x);//双向边
}
cnt=0;
for(register int i=1;i<=n;i++)
if(!dfn[i]) dfs(i,0);//将点全部遍历一遍
for(register int i=1;i<=n;i++){
if(iscut[i]) ++tot;//如果是割顶,总数tot++
}
printf("%d\n",tot);
for(register int i=1;i<=n;i++){
if(iscut[i]) printf("%d ",i);//将是割点的点输出
}
return 0;
}

点双连通分量

来自冯巨佬……

学会了求解割顶,求出BCC就在容易不过了。——冯巨佬

维护一个栈,栈内保存每一次走过的边(一定保存边,因为两个不同的双连通子图可能有交点,但一定没有交边但)。每当发现割顶时,出栈,直到发现当前出栈的边恰好是连接割顶与判定它的子节点的边。则出栈的所有边同属一个双连通子图,这些边的端点也同属一个双连通子图。

代码如下:
因为回溯到根的时候,剩余栈内元素一定是一个双连通子图,故先出栈再特判根。

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
//from 冯巨佬,增加注释
const int CP=1e3+3;
const int CE=CP*CP;

//边表
class fs{
public:
int from,to,nxt;
}E[CE];
int hd[CP],cnt=0;
void add(int x,int y){……}

//bcc
int dfn[CP],low[CP];
int idx=0;

int bel[CP],bcnt=0; //每个点所属的bcc编号,为-1则表示该点是割顶(割顶同时属于两个bcc,所以它的bel无意义)
int stack[CE],top=0;

void tarjan(int cur,int prv)
{
int child = 0;

dfn[cur] = low[cur] = ++idx;

for(int k=hd[cur]; k; k=E[k].nxt)
{
int to=E[k].to;

if(!dfn[to])
{
child++;
stack[++top]=k; //入栈
tarjan(to,cur); //向下搜索

low[cur] = min(low[cur], low[to]);

if(low[to] >= dfn[cur]) //是割顶
{
int pos;
++bcnt;
while(true)
{
pos=stack[top--]; //出栈
bel[E[pos].from] = bel[E[pos].to] = bcnt;
if(E[pos].from==cur && E[pos].to==to) //到达当前的树边
break;//直接退出循环
}
bel[cur] = -1; //标记割顶
}
}
else if(to != prv) low[cur] = min(low[cur], dfn[to]);
}

if(!prv && child==1) //处理根
bel[cur] = bcnt;
}

void bcc() //主求解函数
{
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0);
}

P3225 [HNOI2012]矿场搭建

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

输入输出格式

输入格式:

输入文件有若干组数据,每组数据的第一行是一个正整数 N(N<=500),表示工地的隧道数,接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

输出格式:

输入文件中有多少组数据,输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与:之间无空格,: 之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2642^{64}。输出格式参照以下输入输出样例。

输入输出样例

输入样例#1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
输出样例#1:
1
2
Case 1: 2 4
Case 2: 4 1

说明

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6);

Case 2 的一组解为(4,5,6,7)。

思路

嗯,基本是一个裸的模板题,简化题意:在一个无向图上选择尽量少的点涂黑,使得删除任意一个点后,每个连通分量里都至少有一个黑点。

我们可以求出所有的连通子图,然后判断其中的割点。

若割点为1,则应当将答案+2。为什么?因为,我们应当考虑存在割点的连通块不是点-双连通。就是说,当割点塌陷后,将会分成两个连通块,这两个连通块不能互相到达。

若割点为0,则应当将答案+1。很容易理解。

对于只有一个割顶的连通块,设它的大小为ss,则共有s1s−1种不同的涂黑方案,根据乘法原理将这些s1s−1相乘即可。
对于没有割顶的连通块,方案数为s(s1)/2s∗(s−1)/2,与前面的相乘即可。

code

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>

#define int long long
const int maxn=1e5+10;

struct edge{
int from,to,next;
}map[maxn];

int n,m,dfn[maxn],low[maxn],stk[maxn],top,bcnt,ins[maxn],ans1,ans2,idx;
int cnt,head[maxn];
bool iscut[maxn];
std::vector<int>bcc[maxn];

inline void add(int x,int y){
map[++cnt]=(edge){x,y,head[x]};
head[x]=cnt;
return ;
}

inline void init(){
ans1=bcnt=idx=n=top=cnt=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(iscut,false,sizeof(iscut));
memset(map,0,sizeof(map));
memset(stk,0,sizeof(stk));
memset(head,0,sizeof(head));
memset(ins,0,sizeof(ins));
return ;
}

void dfs(int x,int fa){
dfn[x]=low[x]=++idx;
int child=0;
for(int i=head[x];i;i=map[i].next){
int y=map[i].to;
if(!dfn[y]){
child++;
stk[++top]=i;//栈存边
dfs(y,x);
low[x]=std::min(low[x],low[y]);
if(low[y]>=dfn[x]){
int pos;
bcnt++;
bcc[bcnt].clear();//初始化bcc
while(true){
pos=stk[top--];
if(!ins[map[pos].from]){//如果它不在任何一个连通块中
ins[map[pos].from]=true;
bcc[bcnt].push_back(map[pos].from);
}
if(!ins[map[pos].to]){
ins[map[pos].to]=true;
bcc[bcnt].push_back(map[pos].to);
}
if(x==map[pos].from&&y==map[pos].to) break ;
}
iscut[x]=true,ins[x]=false;
}
}
else low[x]=std::min(low[x],dfn[y]);
}
if(!fa&&child==1) iscut[x]=false;
return ;
}

inline int read(){
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}

signed main(){
int Case=0;
while(scanf("%lld",&m)&&m){
init();
for(register int i=1;i<=m;i++){
int x=read(),y=read();
add(x,y),add(y,x);
n=std::max(n,std::max(x,y));
}
for(register int i=1;i<=n;i++){
if(!dfn[i]) dfs(i,0);
}
ans2=1;
for(int i=1;i<=bcnt;i++){
int cut=0,sz=bcc[i].size();
for(int j=0;j<sz;j++) if(iscut[bcc[i][j]]) ++cut;//统计割点数
if(cut==1) ans1+=1,ans2*=(sz-1);
if(cut==0) ans1+=2,ans2*=(sz*(sz-1))/2;
}
printf("Case %lld: %lld %lld\n",++Case,ans1,ans2);
}
return 0;
}
文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/07/13/割顶&点双连通分量&P3225 [HNOI2012]矿场搭建/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论