题目链接: http://poj.org/problem?id=3352
题目大意：一个连通图中，至少添加多少条边，使得删除任意一条边之后，图还是连通的。
解题思路：
首先来看下边双连通分量的定义：
如果任意两点至少存在两条“边不重复”的路径，那么说这个图是边双连通的。
那么本题中，删除任意一条边，就可以看作是毁掉一条路径，那么只要至少还存在一条路径即可。
也就是说，转化成，求加最少的边，使这个图边双连通。
判断边双连通有两个方法：
①【局限性】编号借助low数组，如果low[u]!=low[v]，就代表这两个点在不同双连通分量中。
这种方法有些小Bug，主要Bug在邻接表这样的不支持重边的数据结构上，如果有重边存在，
那么即使low[u]!=low[v]，u和v也有可能存在于同一个连通分量中。
所以推荐使用链式前向星。
②Tarjin时借助并查集，由于桥（删除之后图就不连通的边）不属于任何双连通分量，所以在Tarjin时，把不是桥的边的u，v并在一起，
表示u，v在同一个双连通分量里，进行缩点。
下面来看一条结论：
若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么
至少增加的边数 =（ 这棵树总度数为1的结点数 + 1 ）/ 2。
这样，只需要统计一下缩点之后每个点的度数即可。
①方法low[u]中存的就是缩点编点，②方法并查集find之后也是缩点编号，degree[编号]记录度数。
注意，由于本题是无向图，对于每条边，只需degree[low[u]]++即可，不用管v。否则每个点的degree要除以2.
最后ans=（leaf+1）/2.
#include "cstdio"
#include "cstring"
#include "iostream"
using namespace std;
#define maxn 2005
struct Edge
{
int to,next;
}e[maxn*];int pre[maxn],dfs_clock,low[maxn],degree[maxn],head[maxn],tol;
void addedge(int u,int v)
{
e[tol].to=v;
e[tol].next=head[u];
head[u]=tol++;
}
int dfs(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to;
if(!pre[v])
{
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
}
else if(pre[v]<pre[u]&&v!=fa) lowu=min(lowu,pre[v]);
}
return low[u]=lowu;
}
int main()
{
//freopen("in.txt","r",stdin);
int n,m,u,v;
while(~scanf("%d%d",&n,&m))
{
memset(head,-,sizeof(head));
memset(pre,,sizeof(pre));
memset(low,,sizeof(low));
memset(degree,,sizeof(degree));
dfs_clock=;tol=;
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i=;i<=n;i++) if(!pre[i]) dfs(i,-);
for(int u=;u<=n;u++)
{
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to;
if(low[u]!=low[v]) degree[low[u]]++;
}
}
int leaf=;
for(int i=;i<=n;i++)
if(degree[i]==) leaf++;
printf("%d\n",(leaf+)/);
}
}
| 2912106 | neopenx | POJ | 3352 | Accepted | 4136 | 16 | C++ | 1589 |
2014-10-31 15:22:43
|