2117?-- Electricity

一個(gè)無向圖 去掉一個(gè)點(diǎn)后最多能被分為多少個(gè)部分

輸入要注意是n m同時(shí)為0才停.... n,m可能有一個(gè)為零 別問我為什么知道...

其實(shí)每太弄懂.....再看看吧

#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; #define ll long long #define rg register const int N=10000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827; int n,m,cnt=0,ans=-inf; int dfn[N],low[N],cut[N],idx=0; template <class t>void rd(t &x){x=0;int w=0;char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=w?-x:x; }int head[N],tot=0; struct edge{int u,v,nxt;}e[N*10]; void add(int u,int v){e[++tot]=(edge){u,v,head[u]};head[u]=tot; }void tarjan(int u,int fa){dfn[u]=low[u]=++idx;for(int i=head[u],v;i;i=e[i].nxt){v=e[i].v;if(!dfn[v]){tarjan(v,u),low[u]=min(low[u],low[v]);if(dfn[u]<=low[v]) ++cut[u];}else if(v!=fa&&dfn[v]<low[u]) low[u]=dfn[v];} }void clean(){tot=idx=cnt=0;ans=-inf;for(int i=0;i<n;++i) head[i]=dfn[i]=cut[i]=low[i]=0; }int main(){while(scanf("%d%d",&n,&m)==2&&(n||m)){clean();for(int i=1,u,v;i<=m;++i) rd(u),rd(v),add(u,v),add(v,u);for(int i=0;i<n;++i)if(!dfn[i]){++cnt;tarjan(i,-1);--cut[i];}for(int i=0;i<n;++i) ans=max(ans,cut[i]);printf("%d\n",ans+cnt);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lxyyyy/p/11168359.html

總結(jié)

以上是生活随笔為你收集整理的【POJ2117】Electricity [tarjan 割点]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。