### The question

Give a picture , If you delete one of the points , So that every other node has a safe exit , At least how many exits need to be set up , How many options are there .

### Solution

Obviously , A map should at least have 2 An exit （ A point biconnected component ）, If you delete points that are not cut points , There's no limit to the answer , The point considered to be deleted is the cut point .

Let's dye the lines beyond the cut point , Each color means that the nodes in the same color should set at least one exit , If a node is dyed in multiple colors , So it shows that it's not optimal to set up an exit here .

### details

ten Tarjan Five mistakes .. Pay attention to the condition of judging the cut point , When judging whether the root of the search tree is a cut point , A little trouble . in addition , Don't cut when dyeing .

### Code

```// bzoj2730
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int maxn=1010;
struct edge {int to,next;}e[maxn<<1];
int cnt,ind,m,n;
void Init() {
cnt=ind=n=0;
memset(vis,0,sizeof(vis));
memset(cut,0,sizeof(cut));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(sum,0,sizeof(sum));
memset(id,0,sizeof(id));
}
}
void Tarjan(int x,int fa,int rt) {
int tot=0;
dfn[x]=low[x]=++ind;
for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) {
if (!dfn[e[i].to]) {
Tarjan(e[i].to,x,rt);
low[x]=min(low[x],low[e[i].to]);
if (low[e[i].to]>=dfn[x] && x!=rt) cut[x]=1; //important
else if (x==rt) tot++;
}
else low[x]=min(low[x],dfn[e[i].to]);
}
if (tot>1) cut[x]=1; //important
}
void dfs(int x,int col) {
vis[x]=cnt;
if (!id[x]) id[x]=col;
else id[x]=-1;
if (vis[e[i].to]!=cnt && !cut[e[i].to]) dfs(e[i].to,col);
}
int main() {
int T=0;
while (1) {
scanf("%d",&m);
if (m==0) break;
printf("Case %d: ",++T);
Init();
for (int u,v,i=1;i<=m;i++) {
scanf("%d%d",&u,&v);
}
for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i,0,i);
cnt=0;int col=0;
for (int i=1;i<=n;i++) if (cut[i]) {
cnt++;
if (vis[e[j].to]!=cnt && !cut[e[j].to]) dfs(e[j].to,++col);
}
for (int i=1;i<=n;i++) if (id[i]!=-1) sum[id[i]]++;
int tot=0;LL ans=1;
for (int i=1;i<=col;i++) if (sum[i]) tot++,ans=ans*sum[i];
if (!tot) printf("2 %d\n",n*(n-1)/2);
else printf("%d %lld\n",tot,ans);
}
return 0;
}
```

## 【bzoj2730】 HNOI2012— More articles on mine construction

2730: [HNOI2012] Mine construction Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1147  Solved: 528[Submit][Statu ...

2. [BZOJ2730][HNOI2012] Mine construction Dot double Cut point

2730: [HNOI2012] Mine construction Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2852  Solved: 1344[Submit][Stat ...

3. BZOJ2730——[HNOI2012] Mine construction

bzoj2730 & world final 2011 H 1. The main idea of the topic : There is an undirected graph , Let you choose a point in it , bring , No matter which point is gone , Other points can reach any point you choose , Minimum output Select a few points ...

4. BZOJ2730 [HNOI2012] Mine construction - Tarjan Cut point

Solution It is not necessary to consider the mine points that have not appeared in the input , So don't worry about it. It's just One point Two connected components of the point . To bring down a mining site , It's equivalent to cutting off this point , So let's find the cut point and the two connected components of the cut point . And then the point double connected component construction ...

5. BZOJ2730: [HNOI2012] Mine construction

Portal The connectivity of a graph must be related to such things as cut points and cut edges . For an undirected graph , After any point is deleted , All points are connected to some specified points . The easier way to solve this problem is to find all the blocks . For a block , If there are two or more in the block ...

6. [BZOJ2730][HNOI2012] Mine construction （ Please cut point ）

subject :http://www.lydsy.com:808/JudgeOnline/problem.php?id=2730 analysis : If the collapse point is not the cut point , That doesn't matter , The point of collapse is the cut point . obviously ...

7. 【 Double connected components 】Bzoj2730 HNOI2012 Mine construction

Description The coal mining site can be regarded as an undirected graph composed of tunnels connecting coal mining points . To be on the safe side , It is hoped that when an accident occurs at the construction site, all the workers at the coal mining point can have a way out and escape to the rescue exit . So the mine owner decided to set up rescue exits at some coal mining sites , So that no matter which ...

8. BZOJ2730:[HNOI2012] Mine construction ( Double connected components )

Description The coal mining site can be regarded as an undirected graph composed of tunnels connecting coal mining points . To be on the safe side , It is hoped that when an accident occurs at the construction site, all the workers at the coal mining point can have a way out and escape to the rescue exit . So the mine owner decided to set up rescue exits at some coal mining sites , So that no matter which ...

9. BZOJ2730 [HNOI2012] Mine construction [ Point biconnected component ]

See delete a point , The rest needs to be connected to the key points , Some people think of finding some pairs , Because it's connected all the time . For an isolated point, double , There are at least two key points . If two points are connected by a cut point , Let's break this cut point , At least one key should be set for each of the two blocks ...

10. [BZOJ2730]:[HNOI2012] Mine construction （ spire ）

Subject portal Title Description The coal mining site can be regarded as an undirected graph composed of tunnels connecting coal mining points . To be on the safe side , It is hoped that when an accident occurs at the construction site, all the workers at the coal mining point can have a way out and escape to the rescue exit . So the mine owner decided to set up rescue exits at some coal mining sites , So that no matter which one ...

## Random recommendation

2. Which of the following does not belong to jdk1.6 Garbage collector ？

Which of the following does not belong to jdk1.6 Garbage collector ? A.  Serail The collector B.  parNew The collector C.  CMS The collector D.  G1 The collector answer :D Explain :Java The development path of garbage collector is shown in the figure below : Its ...

3. 【HTML】HTML Special symbols 【 turn http://www.cnblogs.com/web-d/archive/2010/04/16/1713298.html】

HTML Special character coding encyclopedia : Enter special characters into the web page , Need to be in html Add to the code with & A combination of letters beginning with or marked with &# Number at the beginning . The following is a complete collection of special symbols represented by letters or numbers .                   ...

4. clone github Code for

Terminal execution :git clone Connect .git     # no need sudo

5. c++ Iterative version of linked list merge sort

I used to use js Write a merge sort non recursive version , And this time ,c++ When encapsulating the linked list, we also encounter a merge sort interface . Deng realized the recursive version of merge sort , But the accumulation of recursive call function stack takes up a lot of memory space . So , Then try to implement on the linked list structure to ...

6. URAL 1915 Titan Ruins: Reconstruction of Bygones( Ideas )

It's almost from the beginning to the end of the competition . From self-confidence to wrong To death . This topic can be said to be a question of thinking , Think we just need to understand , This problem becomes the water problem of pure violence , That is, when the number of operands is less than the number of digits in the stack , We don't have ...

7. GDAL Installation and configuration （ compile proj.4）