首页 > 代码库 > HDU 4587 TWO NODES (双连通割点应用)
HDU 4587 TWO NODES (双连通割点应用)
题意:N个点(0~n-1),M条无向边,问去掉2个点后最多的连通分块有多少。
先去掉一个点求出各个割点,并在dfs过程中求出去掉这个割点有多少个连通分块(将iscut[u]=true改为iscut[u]++),
这样子第二次就可以直接找出最多的连通分块了。
#include<iostream> #include<stdio.h> #include<string.h> #include<string> #include<map> #include<stack> #include<queue> #include<vector> #include<stdlib.h> using namespace std; #define M 5005 int pre[M],dfs_clock,iscut[M],low[M],bcc_cnt,bccno[M]; vector<int>G[M],bcc[M]; struct Edge { int from,to; }edge[M*2]; int edge_num,head[M]; void add_edge(int u,int v) { edge[edge_num].from=v; edge[edge_num].to=head[u]; head[u]=edge_num++; } int del; int dfs(int u,int fa) { int lowu=pre[u]=++dfs_clock; for(int i=head[u];i!=-1;i=edge[i].to) { int v=edge[i].from; if(v==del) continue; if(!pre[v]) { int lowv=dfs(v,u); lowu=min(lowv,lowu); if(lowv>=pre[u]) iscut[u]++; } else if(pre[v]<pre[u]&&v!=fa) lowu=min(lowu,pre[v]); } if(fa<0) iscut[u]--; return lowu; } void init() { dfs_clock=0; memset(pre,0,sizeof(pre)); memset(iscut,0,sizeof(iscut)); memset(bccno,0,sizeof(bccno)); } void find_bcc(int n) { int ans=0; for(int i=0;i<n;i++) { init(); del=i; int sum=0; for(int j=0;j<n;j++) { if(j!=i&&!pre[j]) { sum++; dfs(j,-1); } } int maxcut=-1; for(int j=0;j<n;j++) { if(j!=i) maxcut=max(maxcut,iscut[j]); } ans=max(ans,sum+maxcut); } printf("%d\n",ans); } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { int a,b; edge_num=0; memset(head,-1,sizeof(head)); while(m--) { scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } find_bcc(n); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。