poj1523SPF(Tarjan)

http://poj.org/problem?id=1523

参考着各种书籍网上的讲解及各种tarjan算法总算把它捣鼓出来了

这题是求割点及割点分割出来的块数模板题块数利用dfs可加出来

http://blog.csdn.net/lyy289065406/article/details/6752662从这偷来一些知识点

1、【割点】

在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。当割点集合的顶点个数只有1个时，该顶点就是割点。

2、【连通分量】

当删除某个割点后，原图会被划分为若干个互不连通的子图，这些子图就是该割点对应的连通分量。

此时，我们可以得到割点的定义如下：

若有k的儿子为i，我们定义AnceDeep[i]为结点i辈分最高（深度最浅）的祖先的深度，deep[k]为k的搜索深度（时间戳），那么k为割点当且仅当k满足（1）（2）中的一个：

（1）若k为深搜树的根Root，当且仅当k的儿子数（分支数）>=2时k为割点；

（2）若k为搜索树的中间结点（即k既不为根也不为叶），那么k必然有father和son，若AnceDeep[son]>= deep[k]，则k必然为割点。

对于（1）是显然的，根结点k一旦有2个以上的分支，那么删除k必然出现森林；

对于（2）比较难理解，首先注意AnceDeep[son]>= deep[k]这个条件，意思就是“k的儿子son的辈分最高的祖先（暂且设其为w）的深度，比k的深度要深（或者等于k的深度，此时k就是w），就是说k的辈分比w更高（深度更浅），那么一旦删除k，son所在的网络势必和 k的father所在的网络断开”，那么k就是割点。

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stdlib.h>
 5 #include<algorithm>
 6 using namespace std;
 7 struct node
 8 {
 9     int u,v,next;
10 }edge[10100];
11 int t,first[2010],dfn[1010],low[1010],sum[1010],dc,stack[1010],top;
12 void init()
13 {
14     t = 0;
15     memset(first,-1,sizeof(first));
16 }
17 void add(int u,int v)
18 {
19     edge[t].u = u;
20     edge[t].v = v;
21     edge[t].next = first[u];
22     first[u] = t++;
23 }
24 void dfs(int u,int fa)
25 {
26     int i,j;
27     low[u] = dfn[u] = ++dc;
28     int child = 0;
29     for(i = first[u] ; i != -1 ;i = edge[i].next)
30     {
31         int v = edge[i].v;
32         if(!dfn[v])
33         {
34             child++;
35             dfs(v,u);
36             low[u] = min(low[u],low[v]);
37             if(low[u]>=dfn[u])sum[u]++;
38         }
39         else
40         {
41             if(v!=fa)
42             low[u] = min(low[u],dfn[v]);
43         }
44     }
45     if(fa==0)//这为上述判断割点的两种情况
46     {
47         if(child>1)
48         {
49             sum[u] = child;
50             stack[top++]= u;
51         }
52     }
53     else
54     {
55         if(sum[u]>=1)
56         {
57             stack[top++] = u;
58             sum[u]++;
59         }
60     }
61 }
62 int main()
63 {
64     int i,j,k,n,m,a,b,kk=0;
65     while(cin>>a)
66     {
67         if(a==0)break;
68         kk++;
69         top=0;
70         init();
71         memset(dfn,0,sizeof(dfn));
72         memset(low,0,sizeof(low));
73         memset(sum,0,sizeof(sum));
74         cin>>b;
75         add(a,b);add(b,a);
76         while(cin>>a)
77         {
78             if(a==0)break;
79             cin>>b;
80             add(a,b);add(b,a);
81         }
82         n = 1000;
83         dc=0;
84         for(i = 1 ; i <= n ; i++)
85         {
86             if(dfn[i]==0)
87             dfs(i,0);
88         }
89         sort(stack,stack+top);
90         printf("Network #%d\n",kk);
91         for(i = 0 ; i < top ; i++)
92         printf("  SPF node %d leaves %d subnets\n",stack[i],sum[stack[i]]);
93         if(top==0)
94         puts("  No SPF nodes");
95         puts("");
96     }
97     return 0;
98 }