POJ 1253 SPF（tarjan算法求割点）

本文主要是介绍POJ 1253 SPF（tarjan算法求割点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=1523

只要子不能通过子节点回到父节点的父节点的某个节点，那么就能确定这个点是割点

在确定去掉之后有几个分量就是看DFS回来满足几次条件就是几次，注意根节点的处理

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1500;
vector<int> po[maxn];
int now[maxn],small[maxn],rec[maxn],step;
int init(){for(int i=0;i<1001;i++)po[i].clear();step=1;memset(small,0,sizeof(small));memset(now,0,sizeof(now));memset(rec,0,sizeof(rec));return 0;
}
int find_ans(int u){small[u]=now[u]=step++;for(int i=0;i<po[u].size();i++){if(!now[po[u][i]]){find_ans(po[u][i]);small[u]=min(small[u],small[po[u][i]]);if(small[po[u][i]]>=now[u]){rec[u]++;}}else{small[u]=min(small[u],now[po[u][i]]);}}return 0;
}
int main(){int i,k,a,b,c,ca=1;bool flag;while(scanf("%d",&c),c){init();a=c;flag=true;scanf("%d",&b);po[a].push_back(b);po[b].push_back(a);while(scanf("%d",&a),a){scanf("%d",&b);po[a].push_back(b);po[b].push_back(a);}for(i=1;i<1001;i++){if(po[i].size()==0) break;if(!now[i]) find_ans(i);}if(ca>1)putchar('\n');printf("Network #%d\n",ca++);for(i=1;i<1001;i++){if(i==1){if(rec[i]>=2)printf("  SPF node 1 leaves %d subnets\n",rec[i]),flag=false;}else{if(rec[i]){flag=false;printf("  SPF node %d leaves %d subnets\n",i,rec[i]+1);}}}if(flag)printf("  No SPF nodes\n");}return 0;
}

这篇关于POJ 1253 SPF（tarjan算法求割点）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---