题目链接：
POJ1523
题意：
问一个连通的网络中有多少个关节点，这些关节点分别能把网络分成几部分
题解:
Tarjan 算法模板题
顺序遍历整个图，，可以得到一棵生成树：
树边：可理解为在DFS过程中访问未访问节点时所经过的边，也称为父子边回边：可理解为在DFS过程中遇到已访问节点时所经过的边，也称为返祖边、后向边对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；对非叶子节点u（非根节点），若其子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与u的子树的节点不再连通；则节点u为割点。
// 当(u,v)为树边且low[v]>dfn[u]时，表示v节点只能通过该边(u,v)与u连通，那么(u,v)即为割边。
用一个数组保存每个节点的子树个数即可
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#define maxn 1050using namespace std;int dfn[maxn],low[maxn];//dfs序 和子树连接的最小节点int vis[maxn];vector<int>edge[maxn]; int child[maxn];int num,son;void init(){memset(vis,0,sizeof(vis));memset(child,0,sizeof(child));vis[1]=1;num=0;son=0;}void Tarjan(int u){dfn[u]=low[u]=++num;vis[u]=1;for(int i=0; i<edge[u].size(); i++){int v=edge[u][i];if(!vis[v]){Tarjan(v);low[u]=min(low[u],low[v]);if(dfn[u]<=low[v])//得到子树{if(u!=1)child[u]++;elseson++;}}else low[u]=min(low[u],dfn[v]);}}int main(){// freopen("in.txt","r",stdin);int a,b;int Case=1;while(1){while(scanf("%d",&a)&&a){scanf("%d",&b);edge[a].push_back(b);edge[b].push_back(a);}init();Tarjan(1);//for(int i=1;i<=5;i++)//cout<<dfn[i]<<" "<<low[i]<<endl;if(Case>1)cout<<endl;printf("Network #%d\n",Case++);int flag=1;child[1]=son-1;for(int i=1; i<=1000; i++)if(child[i]>0){flag=0;printf(" SPF node %d leaves %d subnets\n",i,child[i]+1);}if(flag)cout<<" No SPF nodes"<<endl;for(int i=1; i<=1000; i++)edge[i].clear();scanf("%d",&a);if(a==0)break;scanf("%d",&b);edge[a].push_back(b);edge[b].push_back(a);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
人生就是要感受美丽的善良的，丑恶的病态的。
