POJ 1523 SPF(割点所割连通分量数)
http://poj.org/problem?id=1523
题意:给你一个无向图,问你该图中有多少割点.且每个割点能把该图分为几个连通分量
分析:本题与POJ 2117很类似,也是用cut[i]数组来计数i节点所能割的儿子数.(不过注意:对于根节点,如果它不是割点,那么cut[i]==0而不是-1了),具体分析完全可以参考POJ 2117:
http://blog.csdn.net/u013480600/article/details/30976823
注意:该题中只有真正的割点其cut值才非0,如果i点不是割点.那么cut[i]==0.(不会存在-1的情况)
对于非根节点的割点,它能分割图为cut[i]+1个连通分量,对于根节点割点,它能分割图为cut[i]个连通分量
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn= 1000+10;
vector<int> G[maxn], ans;
int pre[maxn],cut[maxn],low[maxn];
int dfs_clock;
int tarjan(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
int child=0;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
child++;
int lowv=tarjan(v,u);
lowu=min(lowv,lowu);
if(lowv>=pre[u])
cut[u]++;
}
else if(pre[v]<pre[u] && v!=fa)
lowu=min(lowu,pre[v]);
}
if(fa<0)//根
{
if(child>=2) ans.push_back(u);
}
else if(cut[u]>=1) ans.push_back(u),cut[u]++; //非根割点,所分连通分量还要+1
return low[u]=lowu;
}
int main()
{
int u,v;
int kase=1;
while(scanf("%d",&u)==1&&u)
{
dfs_clock=0;
memset(pre,0,sizeof(pre));
memset(cut,0,sizeof(cut));
ans.clear();
for(int i=1;i<=1000;i++) G[i].clear();
while(true)
{
scanf("%d",&v);
G[u].push_back(v);
G[v].push_back(u);
scanf("%d",&u);
if(u==0) break;
}
for(int i=1;i<=1000;i++)if(pre[i]==0 && G[i].size()>0)
{
tarjan(i,-1);
}
sort(&ans[0],&ans[0]+ans.size());
if(ans.size()>0)
{
printf("Network #%d\n",kase++);
for(int i=0;i<ans.size();i++)
printf(" SPF node %d leaves %d subnets\n",ans[i],cut[ans[i]]);
}
else printf("Network #%d\n No SPF nodes\n",kase++);
puts(""); //别忘了这个回车
}
return 0;
}
分享到:
相关推荐
POJ1523-SPF 【割点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/84AS1D
poj 1523 SPF.md
POJ1523 - SPF 测试数据。 数据来源:Greater New York 2000 问题H
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
80道POJ解题报告及部分源码,本人辛苦收集,希望同仁多多交流,祝AC道路一路顺风!
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这道题的目的是求如去除某个点,能把图分成多少个子图,求这样子图的最大数。...其实就是求割点,然后看每个割点能把图分成多少个子图,当然原图不一定是连通的。 割点的求法各个书籍上都有,其实就是用DFS进行遍历。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等