http://www.lydsy.com/JudgeOnline/problem.php?id=2730 ( Topic link )

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 low[maxn],dfn[maxn],head[maxn],cut[maxn],vis[maxn],id[maxn],sum[maxn];
int cnt,ind,m,n; void Init() {
cnt=ind=n=0;
memset(head,0,sizeof(head));
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 link(int u,int v) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
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;
for (int i=head[x];i;i=e[i].next)
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);
link(u,v);n=max(n,max(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++;
for (int j=head[i];j;j=e[j].next)
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

  1. bzoj2730 [HNOI2012] Mine construction (UVAlive5135 Mining Your Own Business)

    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

  1. Google C++ Unit test framework GoogleTest---Extending Google Test by Handling Test Events

    Google TestExtending Google Test by Handling Test Events Google The test provides an event listener API, Let you receive notifications about the progress of the test program and test failures . ...

  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)

    1. Download address http://trac.osgeo.org/gdal/wiki/DownloadSource Here are two versions : http://pan.baidu.com/s/1bntuXER  (1.1 ...

  8. linux HAProxy And Keepalived Hot standby

    HAProxy It's free , A quick and reliable solution doesn't , It is suitable for those with heavy load web These sites usually need session persistence or seven layer processing to provide high availability , Load balancing and based on tcp and http Agent for application Factors that measure load balancer performance ...

  9. JPA( One ): brief introduction

    JPA What is it? Java Persistence API: For object persistence API Java EE 5.0 Platform standard ORM standard , Enable applications to access the persistence layer in a unified way . JPA and Hibernate The relationship between JP ...

  10. spyder Common functions

    Recently, I discussed with my classmates that spyder Use skills , So combined with the summary of netizens on the Internet before ( https://blog.csdn.net/peiwang245/article/details/78528098) And their ...