矿工安全生产

矿工安全生产

题目链接：https://pta.patest.cn/pta/test/4943/exam/4/question/75471

题目大意：给出$n$条边和若干个点，现要求选择部分点放置逃生装置，使得不管哪个点倒塌，不在此点的所有人都能到达逃生装置逃生。问最少放多少逃生装置，共有几种放置方法.

参考博客：http://blog.csdn.net/jinglinxiao/article/details/64657078

tarjan

当且仅当图中割点被破坏，图的连通性发生改变。故去除割点后连通块的个数即为逃生装置的数量。

任取一点为根，建立一颗DFS树，则树中结点有三种情况：

根结点。根结点有大于$1$颗子树$Leftrightarrow$根为割点；
叶节点。叶节点不为割点；
非根非叶结点。$dfn[i]>low[i] Leftrightarrow i$为割点，其中$dfs[i]$为结点$i$在DFS遍历中的顺序，$low[i]$为$i$及$i$联通的子树中最小的$dfn[j]$.

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <stack>
 7 #include <vector>
 8 using namespace std;
 9 typedef long long ll;
10 vector<int>e[50005];
11 int t,n,root,dfn[50005],low[50005],tot;
12 bool vis[50005],ge[50005];
13 void init(){
14     for(int i=0;i<=50000;++i)e[i].clear();
15     memset(vis,0,sizeof(vis));
16     memset(ge,0,sizeof(ge));
17     tot=0;n=0;root=1;
18     while(t--){
19         int u,v;
20         scanf("%d%d",&u,&v);
21         e[u].push_back(v);
22         e[v].push_back(u);
23         n=max(v,n);
24         n=max(u,n);
25     }
26 }
27 void tar(int u,int p){
28     low[u]=dfn[u]=tot++;
29     vis[u]=1;
30     int cnt=0;
31     for(int i=0;i<(int)e[u].size();++i){
32         int v=e[u][i];
33         if(v==p)continue;
34         if(!vis[v]){
35             tar(v,u);
36             cnt++;
37             low[u]=min(low[u],low[v]);
38         }else low[u]=min(low[u],dfn[v]);
39     }
40     if((u==root&&cnt>1)||(u!=root&&cnt&&low[u]>=dfn[u]))ge[u]=1;
41 }
42 ll dfs(int u){
43     int cnt=1;
44     vis[u]=1;
45     for(int i=0;i<(int)e[u].size();++i){
46         int v=e[u][i];
47         if(!vis[v]&&!ge[v])cnt+=dfs(v);
48     }
49     return cnt;
50 }
51 int main(void){
52     while(scanf("%d",&t)){
53         if(!t)break;
54         init();
55         tar(root,-1);
56         memset(vis,0,sizeof(vis));
57         ll a1=0,a2=1;
58         for(int i=1;i<=n;++i)
59         if(!vis[i]&&!ge[i]){
60             a1++;
61             a2*=dfs(i);
62         }
63         printf("%lld %lld
",a1,a2);
64     }
65 }