hdu4587 Two Nodes 求图中删除两个结点剩余的连通分量的数量

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了hdu4587 Two Nodes 求图中删除两个结点剩余的连通分量的数量，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3623字，纯文字阅读大概需要6分钟。

内容图文

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4587

题目给了12000ms，对于tarjan这种O(|V|+|E|)复杂度的算法来说，暴力是能狗住的。可以对每个点进行枚举，然后对剩余的网络进行tarjan，对割点所能造成的最大的连通分量进行查询，也就是如下的方程。ans=max{cut[i]}+cnt 其中cnt删除第一个结点之后剩下的网络在初始时刻的连通分量的数量，也就是对每一个第一结点tarjan进行深搜的次数。另外，这次的tarjan中的cut数组存储的不再是这个点是否是割点，而是这个点“成为割点的次数”，也就是说，对于一个非根节点u来说，他有k个分支只能通过u来连接到u的祖先，所以u被删除之后就会多出来k个连通分量，这个cut的更新是在搜索完一个分支之后退回到u时更新的。对于根节点来说，由于他没有父结点，原先他所在的连通分量的分量数量为1，现在把它割掉，还剩k个子树的连通分量，也就是根节点使得连通分量的数量增加了k-1，这是不同于非根节点的。

代码如下：（还未解决，WA代码，先暂存着）

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef unsigned int ui;
  4 typedef long long ll;
  5 typedef unsigned long long ull;
  6 #define pf printf
  7 #define mem(a,b) memset(a,b,sizeof(a))
  8 #define prime1 1e9+7
  9 #define prime2 1e9+9
 10 #define pi 3.14159265
 11 #define lson l,mid,rt<<1
 12 #define rson mid+1,r,rt<<1|1
 13 #define scand(x) scanf("%llf",&x) 
 14 #define f(i,a,b) for(int i=a;i<=b;i++)
 15 #define scan(a) scanf("%d",&a)
 16 #define mp(a,b) make_pair((a),(b))
 17 #define P pair<int,int>
 18 #define dbg(args) cout<<#args<<":"<<args<<endl;
 19 #define inf 0x3f3f3f3f
 20 const int maxn=5005;
 21 const int maxm=10010;
 22 int n,m,t;
 23 int head[maxn],nxt[maxn],cut[maxn],dfn[maxn],low[maxn];
 24 struct node{
 25     int u,v;
 26 }p[maxm];
 27 int e;
 28 int first;
 29 int id;
 30 void addedge(int u,int v)
 31 {
 32     p[e].u=u;
 33     p[e].v=v;
 34     nxt[e]=head[u];
 35     head[u]=e++;
 36 }
 37 void tarjan(int u,int fa)
 38 {
 39     dfn[u]=low[u]=++id;
 40     int child=0;
 41     for(int i=head[u];~i;i=nxt[i])
 42     {
 43         int v=p[i].v;
 44         if(v==first||v==fa)continue;//假定了这个网络中没有first结点 
 45         if(!dfn[v])
 46         {
 47             child++;
 48             tarjan(v,u);
 49             low[u]=min(low[u],low[v]);
 50             if(low[v]>=dfn[u]&&u!=fa)cut[u]++;//非根结点成为割点，可割的连通分量的数量增加
 51             if(u==fa&&child>=2)cut[u]++;//根节点，至少有两个子树 
 52         }
 53         else if(dfn[v]<dfn[u]&&v!=fa)
 54         {
 55             low[u]=min(low[u],dfn[v]);
 56         }
 57      }
 58      if(u==fa&&child>=1)cut[u]=child-1;
 59      //更新根节点的cut值的唯一方法是通过子树的数量-1
 60      //注意此时如果根节点的child值是1的话更新之后是0，所以不能加child>1的条件 
 61 }
 62 int main()
 63 {
 64     //freopen("input.txt","r",stdin);
 65     //freopen("output.txt","w",stdout);
 66     std::ios::sync_with_stdio(false);
 67     while(scanf("%d%d",&n,&m)!=EOF)
 68     {
 69         int x,y;
 70         f(i,0,maxn-1)head[i]=-1,nxt[i]=-1;
 71         e=0;
 72         f(i,1,m)
 73         {
 74             scanf("%d%d",&x,&y);
 75             addedge(x,y);
 76             addedge(y,x);
 77         }
 78         int curnum;
 79         int ans=0;
 80         f(i,0,n-1)//枚举每一个点，再用tarjan对割点进行查找，找到割点增加连通分量最多的点。 
 81         {
 82             f(i,0,n-1)dfn[i]=0,cut[i]=0;//要进行n次对这个网络的tarjan，每次都要清零 
 83             first=i;
 84             curnum=0;
 85             id=0;
 86             f(j,0,n-1)
 87             {
 88                 if(i==j)continue;
 89                 if(!dfn[j])
 90                 {
 91                     tarjan(j,j);
 92                     curnum++; 
 93                 }
 94             }
 95             f(j,0,n-1)
 96             {
 97                 if(j!=i) ans=max(ans,curnum+cut[j]);
 98             }
 99         }
100         pf("%d\n",ans);
101     }
102     return 0;
103 } 

 

内容总结

以上是互联网集市为您收集整理的hdu4587 Two Nodes 求图中删除两个结点剩余的连通分量的数量全部内容，希望文章能够帮你解决hdu4587 Two Nodes 求图中删除两个结点剩余的连通分量的数量所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---