POJ2117 Electricity
割点的题
一开始觉得不难想水一发然后就去学别的，然后差点被特判恶心死
其实还是挺水的
求去掉某个点以及与其相连的边，最多可以形成多少个连通分量
图可能不联通
首先，tarjan 求出割点，求割点的同时，统计和这个割点相连的双连通分量有几个
也就是代码中的 (cnt) 数组
然后答案取 (max(cnt))，在加上联通块个数再减一就行了
但是，如果所有联通块，分别多是一整个双联通分量，这样就会出问题
- 如果存在一个大小大于一的联通块，那么答案肯定就是联通块的个数（其实这种情况直接按上面的方法来不特判也可以）
- 但如果所以联通块的个数都是一，就不行了，去掉一个点后，会使联通块个数减少一个，那么答案就是联通块个数减一
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
#define N 100006
#define M 1000006
struct graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
}
inline void clear(){
std::memset(fir,0,sizeof fir);tot=0;
std::memset(to,0,sizeof to);std::memset(nex,0,sizeof nex);
}
}G;
int n,m;
int dfn[N],low[N],dfscnt;
int cnt[N],size[N];
void tarjan(int u,int is_root){
dfn[u]=low[u]=++dfscnt;
for(reg int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(!dfn[v]){
tarjan(v,0);
low[u]=std::min(low[u],low[v]);
if(low[v]>=dfn[u]) cnt[u]++;
}
else low[u]=std::min(low[u],dfn[v]);
}
if(is_root) cnt[u]--;
}
int main(){
n=read();m=read();
while(n){
for(reg int u,v,i=1;i<=m;i++){
u=read()+1;v=read()+1;
G.add(u,v);G.add(v,u);
}
int block=0;
for(reg int i=1;i<=n;i++)if(!dfn[i]){
size[i]=dfscnt;
block++;tarjan(i,1);
size[i]=dfscnt-size[i];
}
int ans=0;
for(reg int i=1;i<=n;i++)if(cnt[i]) ans=std::max(ans,cnt[i]+1);
if(!ans){//特判每个联通分量都是双联通分量的情况
int flag=0;//记录有没有一个联通分量大小大于一
for(reg int i=1;i<=n;i++)if(size[i]>1){
flag=1;break;
}
if(flag) std::printf("%d
",block);
else std::printf("%d
",block-1);//大小全都是 1
}
else std::printf("%d
",ans+block-1);
n=read();m=read();G.clear();
std::memset(dfn,0,sizeof dfn);std::memset(low,0,sizeof low);
std::memset(cnt,0,sizeof cnt);dfscnt=0;
}
return 0;
}