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【割点】"是编程竞赛中的一道题目,涉及图论中的一个重要概念——割点。该题目要求参赛者编写程序来判断一个无向图是否存在割点,并进行相应的处理。割点,也称为关键顶点,是指在无向图中,...
poj 1523 SPF.md
【标题】"POJ1523 - SPF 测试数据"是源于 Greater New York 2000 年编程竞赛中的问题H,这个题目在ACM(国际大学生程序设计竞赛)领域内颇具代表性。SPF全称为Shortest Path First,通常指的是寻找图中最短路径的一...
割点、桥和连通分量是图论中的重要概念,它们在算法设计和图的分析中起到关键作用。在图中,一个割点(Cut vertex)是指删除该点后会使得原来的连通图变为不连通的点,即它的存在维系了某些部分之间的连接。而桥...
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
* 图的割边和割点:例如 poj3352。 * 最小割模型、网络流规约:例如 poj3308。 3. 数据结构: * 线段树:例如 poj2528、poj2828、poj2777、poj2886、poj2750。 * 静态二叉检索树:例如 poj2482、poj2352。 * ...
【标题】"80道POJ解题报告"所涉及的知识点主要集中在ACM(国际大学生程序设计竞赛)和POJ(编程Online Judge系统)上。POJ是北京大学主办的一个在线编程竞赛平台,广泛用于训练和提升程序员的算法设计与实现能力。80...
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
这道题的目的是求如去除某个点,能把图分成多少个子图,求这样子图的最大数。...其实就是求割点,然后看每个割点能把图分成多少个子图,当然原图不一定是连通的。 割点的求法各个书籍上都有,其实就是用DFS进行遍历。
3. **图算法的深化**:如差分约束系统、最小费用最大流、双连通分量、强连通分支及其缩点、图的割边和割点、最小割模型等。poj1201、poj2983等涉及这些高级图算法。 4. **高级数据结构**:如线段树、平衡树(Treap、...
在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支、最小割模型等,以及线段树、树状数组、RMQ查询等高级数据结构的应用。这些内容进一步深化...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
标题中的"POJ第1861题源码"指的是编程竞赛网站POJ(Programming Online Judge)上的第1861道题目,该题目通常会涉及到一个特定的算法或编程问题,而源码则指的是参赛者提交的解决该问题的程序代码。在描述和标签中...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
4. **强连通分量**:识别图中的强连通分量(poj2186)。 5. **割点和桥**:识别图中的关键节点和边(poj3352)。 ### 十二、进阶数据结构 1. **高级数据结构**:如树状数组、线段树(poj2528, poj2828, poj2777, ...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ1011 - Sticks" 是一个经典的计算机编程竞赛题目,源自北京大学的在线评测系统POJ(PKU Online Judge)。这个题目挑战程序员解决与几何图形和数学逻辑相关的问题。 【描述】该题目的核心是求解在二维...
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
- (poj2186):如何找出一个有向图中的强连通分量。 5. **图的同构问题**: - (poj3352):判定两个图是否同构。 6. **小世界模型**: - (poj3308,):探索社交网络中的小世界现象。 ### 九、数据结构进阶 1. **...