NC20099 [HNOI2012]矿场搭建

题目：

• 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。
• 于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。
• 请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

题解：

点双连通分量的性质：

任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性，即BCC中无割点
若BCC间有公共点，则公共点为原图的割点
无向连通图中割点一定属于至少两个BCC，非割点只属于一个BCC

双连通分量重的割点是与其他双连通分量共享的点
• 先找割点和点双联通分量
• 对于一个点双联通分量
• 如果没有割点——2个通道——炸了一个还有一个，方案总数就是Cn^2^
• 一个割点——1个通道——建在不是割点的位置，如果它坍塌了也可以从隔壁的双连通分量里出去，方案总数就是n-1
• 两个割点——0个——不管哪个点塌了都可以从隔壁的双连通分量出去
本题关键在于dfs查找每一个连通块内割点数量

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int head[505],dfn[505],low[505],vis[505],stack[505];
bool cut[505],in_stack[505];
int n,m,cnt,num,tot,deg,ans1,T,cases,root,top;
ll ans2;
struct node
{
    int from;
    int to;
    int next;
}e[1010];
inline void first()
{
    memset(head,0,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(cut,0,sizeof(cut));
    memset(vis,0,sizeof(vis));
    top=cnt=tot=n=ans1=T=0; ans2=1;
}
inline void insert(int from,int to)
{
    e[++num].from=from;
    e[num].to=to;
    e[num].next=head[from];
    head[from]=num;
}
inline int read()
{
    int x=0,f=1; char c=getchar();
    while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}