看了无向图的割点，割边的东西，顺便做了这道题。题目要求出割点以及除去割点后的连通子图的数量。求割点的方法利用深度优先搜索的子数，以及记录结点的访问时间以及结点所能到达的最低祖先，然后对这两个数进行比较从而确定结点是否是割点，求出割点后，要求出此割点去掉后连通子图的数量，一种方法是，对每一个割点，对它的相邻顶点分别进行一次深搜，每搜一次结果加1。但从求割点的过程中分析可知，不通过这样的遍历就可以方便的得到这个结果。用tag[i]标记结点i是否为割点，对于根结点，当搜索它的第一个子树时，由于子树数为1，所以tag[i]仍为零，当每搜索其它一棵子树时，都可以判定根结点是割点，那么tag[i]++, 所以根结点如果是割的情况下它所能形成的连通子图数目为tag[i]+1； 对于非根结点，当第一次遍历到这个结点时，这个结点还不能判断为割点，之后对此结点的每一棵子树，如果能判定i是割点，则tag[i]++, 最后连通子图数还要加上第一次遍历到这个结点时所形成的图，所以总的连通子图数为tag[i]+1。另外此题的结点不一定是连续的。只有1000多个结点，可以直接用邻接矩阵，但要占用比较多的空间。
附上代码：
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