POJ 3177 Redundant Paths(边双连通分量+缩点)
http://poj.org/problem?id=3177
题意:给你一个无向连通图,问你至少需要添加几条边能使得该图是一个边双连通图?
分析:本题与POJ3352基本一样:
http://blog.csdn.net/u013480600/article/details/31004741
首先我们用tarjan求出图中的所有的边双连通分量(对于low[i]值不同的点必然属于不同的分量),然后我们把每个分量看成一个(缩)点,就得到了一个缩点树.
要使得这颗树变成一个边双连通的,
需要添加的边数=(度为1的点数目+1)/2.
注意:此题有重边,需要先去重.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=5000+10;
const int maxm=10000+10;
int n,m;
int dfs_clock;
vector<int> G[maxn];
int pre[maxn],low[maxn],degree[maxn];
void tarjan(int u,int fa)
{
low[u]=pre[u]=++dfs_clock;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
if(!pre[v])
{
tarjan(v,u);
low[u]=min(low[v],low[u]);
}
else low[u]=min(low[u],pre[v]);
}
}
bool A[maxn][maxn]; //错误,之前写成int A[maxn][maxn]
int main()
{
while(scanf("%d%d",&n,&m)==2&&n)
{
dfs_clock=0;
memset(pre,0,sizeof(pre));
memset(degree,0,sizeof(degree));
for(int i=1;i<=n;i++) G[i].clear();
memset(A,0,sizeof(A));
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
A[u][v]=A[v][u]=1; //错误,之前写成A[u][v]=1;
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)if(A[i][j])
{
G[i].push_back(j);
G[j].push_back(i);
}
tarjan(1,-1);
for(int u=1;u<=n;u++)
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(low[u]!=low[v]) //(u,v)是一条跨边双连通分量的边,即缩点树的边
degree[low[v]]++; //错误,这里之前写成了degree[v]++
}
int ans=0;
for(int i=1;i<=n;i++)
if(degree[i]==1) ans++;
printf("%d\n",(ans+1)/2 );
}
return 0;
}
分享到:
相关推荐
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1942-Paths on a Grid 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ2187-Beauty Contest 解题报告+AC代码
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ1416-Shredding Company 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1019-Number Sequence 解题报告+AC代码
北大POJ3126-Prime Path 解题报告+AC代码