POJ 1144 Network(简单求无向图割顶数)
http://poj.org/problem?id=1144
题意:给你一个无向图,问你这个图中有多少个割点.不过该题的输入格式说的比较难懂.这里解释一下:每个实例第一行是N,表示节点数.接下来可能有最多N行描述边信息的.
其中这N行每行都是这样的:每行第一个数表示该行的主顶点u,接着的所有数字表示副顶点v1,v2,v3…等.表示u与v1,u与v2,u与v3分别都有一条边.
最后这个实例以一个0表示结束.
当然所有实例之后还有一个0(N=0),表示输入结束.
分析:直接求割点,用刘汝佳书上的tarjan算法模板即可AC,注意不要把模板打错.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 100+10;
int n;
int dfs_clock;
vector<int> G[maxn];
int pre[maxn],low[maxn];
bool iscut[maxn];
int dfs(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=dfs(v,u);
lowu=min(lowv,lowu);
if(lowv >= pre[u]) //错误1,这里写成了lowu>=pre[u]了
iscut[u]= true;
}
else if(pre[v]<pre[u] && v!=fa)
lowu=min(lowu,pre[v]);
}
if(fa<0 && (child==0||child==1) ) iscut[u]=false;
return low[u]=lowu;
}
int get_v(char *s)
{
int v=0;
for(int i=0;s[i];i++)
v=v*10+s[i]-'0';
return v;
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
dfs_clock=0;
memset(pre,0,sizeof(pre));
memset(iscut,0,sizeof(iscut));
for(int i=1;i<=n;i++) G[i].clear();
char str[10];
while(scanf("%s",str)==1)
{
if(str[0]=='0') break;
int u=get_v(str);
while(scanf("%s",str)==1)
{
int v=get_v(str);
G[u].push_back(v);
G[v].push_back(u);
if(getchar()=='\n') break;
}
}
dfs(1,-1);
int ans=0;
for(int i=1;i<=n;i++)if(iscut[i])
ans++;
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
NULL 博文链接:https://128kj.iteye.com/blog/1720196
这道题的目的是求如去除某个点,能把图分成多少个子图,求这样子图的最大数。 其实就是求割点,然后看每个割点能把图分成多少个子图,当然原图不一定是连通的。 割点的求法各个书籍上都有,其实就是用DFS进行遍历。
北大POJ2531-Network Saboteur 解题报告+AC代码
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 1459 Power Network.md
北大POJ1459-Power Network 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ初级-图算法 解题报告+AC代码
poj分类poj分类poj分类poj分类
利用并查集判断环路,以及快速排序计算最小生成树
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 百练 题目分类 poj 百练 题目分类