A - Network POJ - 1144(割点)

本文主要是介绍A - Network POJ - 1144(割点)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://cn.vjudge.net/contest/258373#problem/A

代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;char m[1000];
vector<int>g[105];
int low[105],dfn[105],vis[105],top;void tarj(int fa,int u)
{low[u]=dfn[u]=++top;//时间戳int child=0;//子树的个数int oo=g[u].size();for(int i=0;i<oo;i++){int v=g[u][i];if(!dfn[v]){++child;tarj(u,v);low[u]=min(low[u],low[v]);//和前面的时间戳比较if(u!=1&&low[v]>=dfn[u]) vis[u]=1;//if不等于根节点，而且他的子图遍历不到时间戳比他小的，为割点}else{low[u]=min(low[u],dfn[v]);//}}if(fa<0&&child>1) vis[u]=1;//if为根节点且子树有大于一个那么根节点为割点
}int main()
{int a;int x,y;while(~scanf("%d",&a)&&a){for(int i=1;i<=a;i++) g[i].clear();while(~scanf("%d",&x)&&x){while(~scanf("%d",&y)){g[x].push_back(y);g[y].push_back(x);if(getchar()=='\n') break;}}memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(vis,0,sizeof(vis));int pp=0;top=0;tarj(-1,1);for(int i=1;i<=a;i++) if(vis[i]) pp++;printf("%d\n",pp);}return 0;
}

 

这篇关于A - Network POJ - 1144(割点)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---