题目大意:给定一个网络,看是否有关节点存在(即割点,即去除该点后,图变成非连通图),如果存在输出该节点和去除该节点后连通子图的个数,如果不存在割点即输出没有割点存在。
求割点直接用dfs解决即可,问题在于统计去除该割点后,连通子图的个数,其实在dfs时,遇到割点时,只要发现其儿子结点的low值比该割点的dfn值大或相等,那么去除该结点后,其儿子结点能到达的所有结点 必定构成一个连通子图,这样用一个son数组记录所有这样的儿子结点的个数,最后加上割点的父亲结点能到达的所有结点形成的连通子图,即为去除该结点后整个图的连通子图的个数。
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 1100;
int ROOT = 1;
#define MIN(a,b) a>b?b:a
#define MAX(a,b) a>b?a:b
int vis[MAXN],cut[MAXN],low[MAXN],dfn[MAXN],son[MAXN],p[MAXN],used[MAXN];
vector<int> g[MAXN];
void init()
{
memset(vis,0,sizeof(vis));
memset(cut,0,sizeof(cut));
memset(son,0,sizeof(son));
memset(used,0,sizeof(used));
for(int i=0;i<MAXN;i++)g[i].clear(),p[i]=i;
}
int find(int x)
{
return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1==r2)return;
p[r1]=r2;
}
int conn()
{
int cnt =0;
for(int i=0;i<MAXN;i++)
{
if(p[i]==i&&used[i])cnt++;
}
return cnt;
}
void dfs(int u,int father,int deep)
{
vis[u] = 1;
dfn[u] = low[u] = deep;
int s = 0,record = 0;
for(int i=0;i<g[u].size();i++)
{
int v = g[u][i];
if(!vis[v])
{
dfs(v,u,deep+1);
s++;
low[u] = MIN(low[u],low[v]);
if((u==ROOT&&s>=2)||(u!=ROOT&&low[v]>=dfn[u]))
{
cut[u] = 1;record++;
}
}
else if(v!=father)
{
low[u] = MIN(low[u],dfn[v]);
}
}
son[u] = record;
}
int main()
{
int u,v;init();int cas=0,start=1;
while(scanf("%d",&u))
{
if(u!=0)
{
start = 0;
scanf("%d",&v);
g[u].push_back(v);
g[v].push_back(u);
used[u] = used[v] = 1;
merge(u,v);
continue;
}
if(u==0&&start)break;
for(int i=0;i<MAXN;i++)
{
if(!vis[i]&&used[i])
{
ROOT = i;
dfs(ROOT,-1,0);
}
}
bool flag = false;int cnt = conn();
printf("Network #%d\n",++cas);
for(int i=0;i<MAXN;i++)
{
if(cut[i])
{
flag = true;
printf(" SPF node %d leaves %d subnets\n",i,son[i]+cnt);
}
}
if(!flag)
{
printf(" No SPF nodes\n");
}
printf("\n");
init();start = 1;
}
return 0;
}
分享到:
相关推荐
POJ1523-SPF 【割点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/84AS1D
2遍dp poj_3613解题报告 poj_3613解题报告
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj题目2775文件子目录源代码,递归经典题目,
poj 1699的代码和方法说明,个人原创
O(nlogn)凸包问题 poj2187
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
POJ 3131 双向BFS解立体八数码问题
poj两道题的c++实现。已经测试过可以通过oj
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
这道题的目的是求如去除某个点,能把图分成多少个子图,求这样子图的最大数。...其实就是求割点,然后看每个割点能把图分成多少个子图,当然原图不一定是连通的。 割点的求法各个书籍上都有,其实就是用DFS进行遍历。
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。