首页 > 代码库 > HDU 4587 TWO NODES（割两个点的最大连通分支数）
HDU 4587 TWO NODES（割两个点的最大连通分支数）
http://acm.hdu.edu.cn/showproblem.php?pid=4587
题意：
给一图，求割去两个点后所能形成的最大连通分支数。
思路：
对于这种情况，第一个只能枚举，然后在删除第一个点的前提下，用Tarjan算法求第二个割点的情况。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,ll> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=5000+5; 17 18 int n, m; 19 int tot; 20 int dfs_clock; 21 int pre[maxn]; 22 int cut[maxn]; 23 int low[maxn]; 24 int head[2*maxn]; 25 int del; 26 27 struct node 28 { 29 int v,next; 30 }e[2*maxn]; 31 32 void addEdge(int u, int v) 33 { 34 e[tot].v=v; 35 e[tot].next=head[u]; 36 head[u]=tot++; 37 } 38 39 int tarjan(int u, int fa) 40 { 41 int lowu=pre[u]=++dfs_clock; 42 for(int i=head[u];i!=-1;i=e[i].next) 43 { 44 int v=e[i].v; 45 if(v==del) continue; 46 if(!pre[v]) 47 { 48 int lowv = tarjan(v,u); 49 lowu=min(lowu,lowv); 50 if(lowv>=pre[u]) cut[u]++; 51 } 52 else if(v!=fa) 53 lowu=min(lowu,pre[v]); 54 } 55 if(fa<0) cut[u]--; 56 return low[u]=lowu; 57 } 58 59 int solve() 60 { 61 int cnt=0; 62 dfs_clock=0; 63 memset(cut,0,sizeof(cut)); 64 memset(pre,0,sizeof(pre)); 65 for(int i=0;i<n;i++) 66 { 67 if(del!=i && !pre[i]) 68 { 69 cnt++; 70 tarjan(i,-1); 71 } 72 } 73 int ans=0; 74 for(int i=0;i<n;i++) 75 { 76 if(i!=del) ans=max(ans,cnt+cut[i]); 77 } 78 return ans; 79 } 80 81 int main() 82 { 83 //freopen("in.txt","r",stdin); 84 while(~scanf("%d%d",&n,&m)) 85 { 86 tot=0; 87 memset(head,-1,sizeof(head)); 88 for(int i=0;i<m;i++) 89 { 90 int u,v; 91 scanf("%d%d",&u,&v); 92 addEdge(u,v); 93 addEdge(v,u); 94 } 95 int ans=-1; 96 for(int i=0;i<n;i++) 97 { 98 del=i; 99 ans=max(ans,solve());100 }101 printf("%d\n",ans);102 }103 return 0;104 }
HDU 4587 TWO NODES（割两个点的最大连通分支数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。