看了無向圖的割點，割邊的東西，順便做了這道題。題目要求出割點以及除去割點后的連通子圖的數(shù)量。求割點的方法利用深度優(yōu)先搜索的子數(shù)，以及記錄結(jié)點的訪問時間以及結(jié)點所能到達的最低祖先，然后對這兩個數(shù)進行比較從而確定結(jié)點是否是割點，求出割點后，要求出此割點去掉后連通子圖的數(shù)量，一種方法是，對每一個割點，對它的相鄰頂點分別進行一次深搜，每搜一次結(jié)果加1。但從求割點的過程中分析可知，不通過這樣的遍歷就可以方便的得到這個結(jié)果。用tag[i]標記結(jié)點i是否為割點，對于根結(jié)點，當搜索它的第一個子樹時，由于子樹數(shù)為1，所以tag[i]仍為零，當每搜索其它一棵子樹時，都可以判定根結(jié)點是割點，那么tag[i]++, 所以根結(jié)點如果是割的情況下它所能形成的連通子圖數(shù)目為tag[i]+1； 對于非根結(jié)點，當?shù)谝淮伪闅v到這個結(jié)點時，這個結(jié)點還不能判斷為割點，之后對此結(jié)點的每一棵子樹，如果能判定i是割點，則tag[i]++, 最后連通子圖數(shù)還要加上第一次遍歷到這個結(jié)點時所形成的圖，所以總的連通子圖數(shù)為tag[i]+1。另外此題的結(jié)點不一定是連續(xù)的。只有1000多個結(jié)點，可以直接用鄰接矩陣，但要占用比較多的空間。
附上代碼：
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