看了無(wú)向圖的割點(diǎn)，割邊的東西，順便做了這道題。題目要求出割點(diǎn)以及除去割點(diǎn)后的連通子圖的數(shù)量。求割點(diǎn)的方法利用深度優(yōu)先搜索的子數(shù)，以及記錄結(jié)點(diǎn)的訪問(wèn)時(shí)間以及結(jié)點(diǎn)所能到達(dá)的最低祖先，然后對(duì)這兩個(gè)數(shù)進(jìn)行比較從而確定結(jié)點(diǎn)是否是割點(diǎn)，求出割點(diǎn)后，要求出此割點(diǎn)去掉后連通子圖的數(shù)量，一種方法是，對(duì)每一個(gè)割點(diǎn)，對(duì)它的相鄰頂點(diǎn)分別進(jìn)行一次深搜，每搜一次結(jié)果加1。但從求割點(diǎn)的過(guò)程中分析可知，不通過(guò)這樣的遍歷就可以方便的得到這個(gè)結(jié)果。用tag[i]標(biāo)記結(jié)點(diǎn)i是否為割點(diǎn)，對(duì)于根結(jié)點(diǎn)，當(dāng)搜索它的第一個(gè)子樹(shù)時(shí)，由于子樹(shù)數(shù)為1，所以tag[i]仍為零，當(dāng)每搜索其它一棵子樹(shù)時(shí)，都可以判定根結(jié)點(diǎn)是割點(diǎn)，那么tag[i]++, 所以根結(jié)點(diǎn)如果是割的情況下它所能形成的連通子圖數(shù)目為tag[i]+1； 對(duì)于非根結(jié)點(diǎn)，當(dāng)?shù)谝淮伪闅v到這個(gè)結(jié)點(diǎn)時(shí)，這個(gè)結(jié)點(diǎn)還不能判斷為割點(diǎn)，之后對(duì)此結(jié)點(diǎn)的每一棵子樹(shù)，如果能判定i是割點(diǎn)，則tag[i]++, 最后連通子圖數(shù)還要加上第一次遍歷到這個(gè)結(jié)點(diǎn)時(shí)所形成的圖，所以總的連通子圖數(shù)為tag[i]+1。另外此題的結(jié)點(diǎn)不一定是連續(xù)的。只有1000多個(gè)結(jié)點(diǎn)，可以直接用鄰接矩陣，但要占用比較多的空間。
附上代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #define N 1050
4 int w[N][N];
5 int n;
6 int m;
7 int time;
8 int dis[N];
9 int low[N];
10 int tag[N];
11 void dfs(int v,int prt)
12 {
13 time++;
14 dis[v]=low[v]=time;
15 int child=0;
16 int i;
17 for(i=m;i<=n;++i)
18 {
19 if(w[v][i]==0) continue;
20 if(i!=prt&&dis[i]>0)
21 {
22 if(dis[i]<low[v])
23 low[v]=dis[i];
24 }else if(dis[i]==0)
25 {
26 child++;
27 dfs(i,v);
28 if(low[i]<low[v])
29 low[v]=low[i];
30 if((v!=m&&dis[v]<=low[i])||(child>=2&&v==m))
31 tag[v]++;
32 }
33 }
34 }
35 void input()
36 {
37 int a,b;
38 int cur=0;
39 while(scanf("%d",&a)&&a!=0)
40 {
41 scanf("%d",&b);
42 n=0;
43 m=1005;
44 memset(w,0,sizeof(w));
45 w[a][b]=w[b][a]=1;
46 if(a>n) n=a;
47 if(b>n) n=b;
48 if(a<m) m=a;
49 if(b<m) m=b;
50 while(scanf("%d",&a)&&a!=0)
51 {
52 scanf("%d",&b);
53 w[a][b]=w[b][a]=1;
54 if(a>n) n=a;
55 if(b>n) n=b;
56 if(a<m) m=a;
57 if(b<m) m=b;
58 }
59 memset(tag,0,sizeof(tag));
60 memset(dis,0,sizeof(dis));
61 memset(low,0,sizeof(low));
62 time=0;
63 dfs(m,0);
64 int i,j,bb;
65 bb=0;
66 printf("Network #%d\n",++cur);
67
68 for(i=m;i<=n;++i)
69 {
70 if(tag[i])
71 {
72 bb=1;
73 printf(" SPF node %d leaves %d subnets\n",i,tag[i]+1);
74
75 }
76 }
77 if(!bb) printf(" No SPF nodes\n");
78 printf("\n");
79 }
80 }
81
82 int main()
83 {
84 input();
85 return 1;
86 }
87