至少加幾條邊成為雙連通分量

?

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=10000; struct {int to,next; }e[maxn]; int head[maxn],lon; int dfn[maxn],instack[maxn],low[maxn],stack[maxn],s[maxn]; int in[maxn]; int count,top,con; int n,m; void edgemake(int from,int to,int head[]) {e[++lon].to=to;e[lon].next=head[from];head[from]=lon; } void edgeini() {memset(head,-1,sizeof(head));lon=-1; }void tarjan(int t,int from) {dfn[t]=low[t]=++count;instack[t]=1;stack[++top]=t;for(int k=head[t];k!=-1;k=e[k].next){if(k==(from^1)) continue;int u=e[k].to;if(dfn[u]==-1){tarjan(u,k);low[t]=min(low[t],low[u]);}else if(instack[u]){low[t]=min(low[t],dfn[u]);}}if(dfn[t]==low[t]){++con;while(1){int u=stack[top--];instack[u]=0;s[u]=con;if(u==t) break;}} }void tarjan()//tarjan的初始化 {memset(dfn,-1,sizeof(dfn));memset(instack,0,sizeof(instack));count=top=con=0;for(int i=1;i<=n;i++)if(dfn[i]==-1)tarjan(i,-1); }int main() {while(scanf("%d %d",&n,&m)!=EOF){edgeini();for(int i=1,from,to;i<=m;i++){scanf("%d %d",&from,&to);edgemake(from,to,head);edgemake(to,from,head);}tarjan();memset(in,0,sizeof(in));for(int i=1;i<=n;i++)for(int k=head[i];k!=-1;k=e[k].next)if(s[i]!=s[e[k].to]){in[s[i]]++;}int ans=0;for(int i=1;i<=con;i++)if(in[i]==1)ans++;else if(in[i]==0)ans+=2;if(con==1) ans-=2;printf("%d\n",(ans+1)/2);}return 0; }

?

?

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

總結(jié)

以上是生活随笔為你收集整理的poj 3352 双连通分量的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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