停电，漆黑的夜晚。
ACM + +是一家电力公司。该公司拥有数个发电厂，每一个供应一个小面积，这些发电厂给这个公司带来了很多的麻烦，在某些地区没有足够的电力，而在其他地区却有大量的盈余。
ACM ++因此决定将一些发电厂连接成一个网络。当然第一阶段，没有必要将所有的发电厂连接到一个网络，但另一方面，它必须在关键地方建立冗余连接，即网络不保证是连通的。现在提出了各种连接的计划，并已开始复杂的评估。
必须考虑的评估标准之一是创建的网络的可靠性。我们假设可以发生的最坏的事件是一个发电厂故障，这可能会导致网络分成几个部分。虽然每一部分都可以工作，但被分成的部分越多，麻烦可能性就越大。因此，我们必须找出所有方案中，某个电厂故障，会形成的最大块数。
输入由若干实例组成。
每个实例第一行都包含两个整数P和C（1 <= P = 10,000，C >= 0），中间用空格隔开。P是电厂的数量。电厂编号为0到P - 1之间的整数。C是边数。下面的C行，每一行包含两个整数0 < = P1，P2＜P用一个空格隔开，这意味着电厂P1和P2连接。每个连接不会重复描述。输入终止的行包含两个零。
输出由若干行组成。输出的第i行对应于第i个输入实例。输出的每一行由一个整数组成，即通过在实例中删除一个连接点，最多可以使网络分成的最大块数。
时间：1s 空间：64M
1 <= P = 10,000
注意没有边的情况
题解：困了，真的好累想睡觉……这篇是别人的，有空我一定会补上！ #include<cstdio> #include<iostream> #include<cstring> using namespace std; const int Maxn=100005; int n,m,cnt,h[Maxn],dfn[Maxn],low[Maxn],ti,cut[Maxn],ans,sum; struct node{ int v,next; }e[Maxn*2]; inline int mn(int x,int y){ return x<y?x:y; } inline int mx(int x,int y){ return x>y?x:y; } inline int read(){ int x=0;char c=getchar(); while(c<'0'||c>'9'){ c=getchar(); } while(c<='9'&&c>='0'){ x=x*10+c-'0'; c=getchar(); } return x; } void add(int u,int v){ cnt++; e[cnt].v=v; e[cnt].next=h[u]; h[u]=cnt; } void dfs(int u,int fa){ dfn[u]=low[u]=++ti; for(int i=h[u];i;i=e[i].next){ int v=e[i].v; if(v==fa)continue; if(!dfn[v]){ dfs(v,u); low[u]=mn(low[u],low[v]); if(low[v]>=dfn[u]){ cut[u]++; } } else{ low[u]=mn(low[u],dfn[v]); } } } int main(){ int u,v; while(1){ memset(h,0,sizeof(h)); memset(dfn,0,sizeof(dfn)); memset(cut,0,sizeof(cut)); ans=-1;sum=cnt=ti=0; n=read();m=read(); if(n==0&&m==0)return 0; if(m==0){printf("%d\n",n-1);continue;} for(int i=1;i<=m;++i){ u=read();v=read(); add(u,v); add(v,u); } for(int i=0;i<n;++i){ if(!dfn[i]){ cut[i]=-1; dfs(i,-1); sum++; } } for(int i=0;i<n;++i){ ans=mx(ans,cut[i]); } printf("%d\n",ans+sum); } return 0; }
转载于:https://www.cnblogs.com/wuhu-JJJ/p/11154935.html
