POJ 1144 Network(无向图连通分量求割点)
2024-09-04 18:10:23
题目地址: id=1144">POJ 1144
求割点。推断一个点是否是割点有两种推断情况:
假设u为割点,当且仅当满足以下的1条
1、假设u为树根,那么u必须有多于1棵子树
2、假设u不为树根。那么(u,v)为树枝边。当Low[v]>=DFN[u]时。
然后依据这两句来找割点就能够了。
代码例如以下:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm> using namespace std;
int head[200], cnt, index1, ans;
int vis[200], low[200], dfn[200], ge[200];
struct node
{
int u, v, next;
}edge[2000];
void add(int u, int v)
{
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void tarjan(int u, int fa)
{
int son=0, i;
low[u]=dfn[u]=++index1;
vis[u]=1;
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
son++;
if(!vis[v])
{
tarjan(v,u);
low[u]=min(low[v],low[u]);
if(u==1&&son>1||dfn[u]<=low[v]&&u!=1)
{
ge[u]++;
}
}
else if(v!=fa)
low[u]=min(low[u],dfn[v]);
}
}
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
index1=ans=0;
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(ge,0,sizeof(ge));
}
int main()
{
int n, i, j, u, v;
while(scanf("%d",&n)!=EOF&&n)
{
init();
while(scanf("%d",&u)!=EOF&&u)
{
while(getchar()!='\n')
{
scanf("%d",&v);
add(u,v);
add(v,u);
}
}
tarjan(1,-1);
for(i=1;i<=n;i++)
{
if(ge[i])
ans++;
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- Mahout推荐算法API详解
- 手把手教你玩转nginx负载均衡(二)----安装虚拟机操作系统
- sql查询单个银行账号重复
- Hive 实战(2)--hive分区分桶实战
- BZOJ 1001 &; SPFA
- java基础语法知识
- spring中的aware接口
- 结果集一组数据的第几条ROW_NUMBER基本用法
- iOS开发之Runtime函数
- 网易云课堂_C++程序设计入门(上)_第1单元:C++概览_第1单元作业 - 写代码 - 互评 (难度:易)
- Visual Studio 2010 将网站直接发布到远程站点
- robots.txt 文件指南
- 【开源.NET】 分享一个前后端分离的轻量级内容管理框架
- Android Studio中添加SlidingMenu
- TurnipBit:和孩子一起动手DIY“滚动”的生日礼物
- wampserver 的Apache启动错误提示:The requested URL / was not found on this server.
- Linux SendMail发送邮件失败诊断案例(四)
- Java的String和StringBuilder
- 定时清理elasticsearch
- ASP.NET MVC3 学习心得------路由机制