POJ1144 Network(判断割点)
题目链接“点击打开链接
判断割点的个数
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> const int N = 210; const int maxn = 500; const int maxm = 21010; const int inf = 1e8; #define MIN INT_MIN #define MAX 1e6 #define LL long long #define init(a) memset(a,0,sizeof(a)) #define FOR(i,a,b) for(int i = a;i<b;i++) #define max(a,b) (a>b)?(a):(b) #define min(a,b) (a>b)?(b):(a) using namespace std; int DFN[maxn],low[maxn],head[maxn]; bool dian[maxn]; int bianhao,n,bnum,root,vis[maxn]; int gedian[maxn],ge; struct edge { int v,next; }edge[maxm]; void add(int u,int v) { edge[bnum].v=v; edge[bnum].next=head[u]; head[u]=bnum++; } void tarjan(int u,int father)//判定割点 { int son=0; vis[u]=1;//标记 DFN[u]=low[u]=bianhao++; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(vis[v]==1 && v!=father) low[u]=min(low[u],DFN[v]); if(vis[v]==0) { tarjan(v,u); son++; low[u]=min(low[u],low[v]); if((u==root && son>1 ) || (u!=root && DFN[u]<=low[v]))//判定割点的条件 { dian[u]=1; } } } vis[u]=2;//去掉 } void initt() { memset(head,-1,sizeof(head)); init(DFN);init(low); init(vis);init(dian); bnum=0;bianhao = 1;//ge = 0; } int main() { int a,b; while(scanf("%d",&n),n) { initt(); while(scanf("%d",&a),a) { while(getchar()!='\n') { scanf("%d",&b); add(a,b); add(b,a); } } root=1; tarjan(1,-1); int ans = 0; FOR(i,1,n+1) { if(dian[i]!=0) { ans++; // gedian[ge++] = i; } } cout<<ans<<endl; // puts("割点是"); /* printf("ge = %d\n",ge); FOR(i,0,ge) printf("%d ",gedian[i]); printf("\n");*/ } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。