首页 > 代码库 > UVA315 Network 连通图割点
UVA315 Network 连通图割点
题目大意:有向图求割点
题目思路:
一个点u为割点时当且仅当满足两个两个条件之一:
1.该点为根节点且至少有两个子节点
2.u不为树根,且满足存在(u,v)为树枝边(或称 父子边,即u为v在搜索树中的父亲),使得 dfn(u)<=low(v)。
然后注意读入,很容易RE
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<iostream> #include<algorithm> #define MAXSIZE 1005 #define LL long long using namespace std; int vis[MAXSIZE],Map[MAXSIZE][MAXSIZE],low[MAXSIZE],dfn[MAXSIZE],pre[MAXSIZE],Time,n,ans,son; void Tarjan(int u,int fa) { pre[u]=fa; low[u]=dfn[u]=++Time; for(int i=1; i<=n; i++) { if(!Map[u][i] || u==i) continue; if(!dfn[i]) { Tarjan(i,u); low[u]=min(low[u],low[i]); } else if(fa!=i) { low[u]=min(low[u],dfn[i]); } } } void Init() { memset(Map,0,sizeof(Map)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis)); memset(pre,0,sizeof(pre)); Time=0; ans=0; son=0; } int main() { int a,b; char ch,op; while(scanf("%d",&n),n) { Init(); getchar(); while(scanf("%d",&a),a) { while(scanf("%d%c",&b,&op)) { Map[a][b]=Map[b][a]=1; if(op==‘\n‘) break; } } Tarjan(1,0); for(int i=2;i<=n;i++) { if(pre[i]==1) son++; else if(dfn[pre[i]] <= low[i]) vis[pre[i]]=1; } if(son > 1) ans++; for(int i=2;i<=n;i++) if(vis[i]) ans++; printf("%d\n",ans); } return 0; }
UVA315 Network 连通图割点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。