POJ1523 SPF(割点模板)

题目求一个无向图的所有割点,并输出删除这些割点后形成几个连通分量。用Tarjan算法:

一遍DFS,构造出一颗深度优先生成树,在原无向图中边分成了两种:树边(生成树上的边)和反祖边(非生成树上的边)。

顺便求出每个结点的DFS序dfn[u] 和 每个结点能沿着它和它的儿子的返祖边达到的结点最小的DFS序low[u]

一个点是割点当且仅当——

  • 这个点是生成树的根,且有x(x>=2)个的子树,删除这个点后就形成x个连通分量。
  • 这个点不是树根,且其存在x(x>=1)个儿子的low值大于等于该点的dfn值,删除该点后就形成x+1个连通分量。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAXM 1111*1111*2
 6 #define MAXN 1111
 7 struct Edge{
 8     int v,next;
 9 }edge[MAXM];
10 int head[MAXN],NE;
11 void addEdge(int u,int v){
12     edge[NE].v=v; edge[NE].next=head[u]; head[u]=NE++;
13 }
14 int dn,dfn[MAXN],low[MAXN],son[MAXN];
15 void dfs(int u){
16     dfn[u]=low[u]=++dn;
17     for(int i=head[u]; i!=-1; i=edge[i].next){
18         int v=edge[i].v;
19         if(dfn[v]){
20             low[u]=min(low[u],dfn[v]);
21             continue;
22         }
23         dfs(v);
24         if(u==1) ++son[u];
25         else if(low[v]>=dfn[u]) ++son[u];
26         low[u]=min(low[u],low[v]);
27     }
28 }
29 bool output(){
30     bool flag=0;
31     if(son[1]>=2) printf("  SPF node 1 leaves %d subnets
",son[1]),flag=1;
32     for(int u=2; u<=1000; ++u){
33         if(son[u]) printf("  SPF node %d leaves %d subnets
",u,son[u]+1),flag=1;
34     }
35     return flag;
36 }
37 int main(){
38     int u,v,t=0;
39     for(;;){
40         bool flag=1;
41         NE=0;
42         memset(head,-1,sizeof(head));
43         while(~scanf("%d",&u) && u){
44             scanf("%d",&v);
45             addEdge(u,v); addEdge(v,u);
46             flag=0;
47         }
48         if(flag) break;
49         dn=0;
50         memset(dfn,0,sizeof(dfn));
51         memset(son,0,sizeof(son));
52         dfs(1);
53         printf("Network #%d
",++t);
54         if(!output()) puts("  No SPF nodes");
55         putchar('
');
56     }
57     return 0;
58 }
原文地址:https://www.cnblogs.com/WABoss/p/5153923.html