poj 2117 Electricity (无向图割点去除后最大连通分支数)

60 阅读 0 评论 40 点赞

我是靠谱客的博主顺心星星，最近开发中收集的这篇文章主要介绍poj 2117 Electricity (无向图割点去除后最大连通分支数)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：求去除一点后，形成的连通分支数的最大值。（使最多的网络不能跟原路线相连）

顶点u是割项当且仅满足（1）或（2）时：

（1）若u是树根，且u的孩子数 son>1 。因为没有u的后向边，以这些孩子为根的子树之间互不相连通，所以去掉u后将得到son个分支。

（2）若u不是树根，且存在树边 ( u , v ) 使low ( v ) >= dfn ( u )。low值说明以v为根的子树不能到达u的祖先也就是去掉u后不能跟原图连通。（跟割绳子一样，一条绳子割n刀会形成 (n +1) 小段）所以得到 { 这样的v的个数 + 1 }个分支。

另外需要注意：

1. 若整个图没有边，则去掉一个点后，连通分支量为所有顶点数 -1 。

2. 因为是无向图，所以每个有边相连的子图都是一个连通分支。比如：

n = 4 m = 2 ：（0 ， 1）（2 ， 3）就是两个连通分支。

n = 3 m = 3 ：（ 0 ， 1）（1 ， 2 ）（2 ， 0）整个图就是一个联通分支。

所以： ans =( 没有去除顶点u时的联通分支 - 1 ) + 去除顶点后新增的分支数。

代码：

#include<iostream>
#include<string.h>
#include<vector>
#define mm 10010
using namespace std;
vector <int> vec[mm];
int
low[mm] , dfn[mm]
;
int step
, son ,
ans , ma;
int n, m
;
void init()
{
for(int i=0;i<mm;i++)
{
low[i]=dfn[i]= 0;
vec[i].clear();
}
step=son= ans=ma=0;
}
void insert(int u , int v)
{
vec[u].push_back(v);
vec[v].push_back(u);
}
void tarjan(int u , int rt)
{
int v;
low[u]=dfn[u]=++step;
int child=0;
//之前将该变量定为了全局，导致错误（每次递归都会改变）
//而局部变量中，只有在同一个递归层才能改变child的值。
for(int i=0;i<vec[u].size(); i++)
{
v=vec[u][i];//cout<<"u= "<<u<<endl;
if(!dfn[v])
{
tarjan(v , rt);
low[u]=min(low[u] , low[v]);
if(u==rt) son++;
else if(low[v]>=dfn[u])
{//cout<<u<<"--------"<<v<<endl;
child++;
}
}
else low[u]=min(dfn[v] , low[u]);
}
cout<<"u= "<<u<<"
rt= "<<rt<<endl;
cout<<"son= "<<son<<"
child+1= "<<child+1<<endl;
ans=max(child+1 , ans);
}
int main()
{
int a , b ,num;
while(scanf("%d%d",&n,&m)!=EOF && n+m)
{
init();
num=0;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a, &b);
insert(a , b);
}
for(int i=0;i<n;i++)
{
if(!dfn[i])
{num++;
son =0;
//
memset(dfn,0,sizeof(dfn));
tarjan(i , i);
if(son>1)
ans=max(ans , son);
ma=max(ma, ans);
}//cout<<"ma= "<<ma<<"
num= "<<num<<"
sum= "<<sum<<endl;
}
if(m==0) ma=0;
printf("%dn", num+ma-1);
}
return 0;
}