题意：给出一个网络（不一定连通），求所有的割点，以及割点可以切分出多少个连通分量。
思路：很多种情况。
（1）如果给的图已经不是连通图，直接“ No SPF nodes”。
（2）求所有割点应该不难，就是tarjan发明的算法搞定。但是求连通分量就得小心了，多种情况。看下：
1）如果一个割点x，其所有孩子都不是割点，那么x至少可以割出两个连通分量（x之上和之下的各1个）。
2）如果一个割点x，其有部分孩子是割点，有部分孩子并不是割点，那么x可以割出x之上的1个连通分量，不是割点的孩子均是同1个连通分量，是割点的孩子各自分别是一个连通分量。
3）如果一个割点x，如果有些孩子是叶子节点，且该叶子节点的度为1，即连着x，那么该叶子节点会被割出来，单点也是连通分量。
1 //#include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int N=1005; 10 int mapp[N][N]; 11 int cntr, flag, up; //时间戳 12 int dfn[N], low[N], vis[N], iscut[N], cur[N]; //记录时间戳， 反边最顶点， 访问记录， 是否连通分量 13 14 bool DFS(int x, int far) 15 { 16 int chd=0; //孩子节点个数 17 int cnt=0, sum=0; 18 dfn[x]=low[x]=++cntr; //时间戳 19 vis[x]=1; //DFS必备 20 for(int i=1; i<=up; i++) 21 { 22 if(!mapp[i][x]) continue; 23 if(!vis[i]) //树边 24 { 25 chd++; 26 bool f=DFS(i,x); //i点只有一条边 27 low[x]=min(low[x],low[i]); 28 29 //判断连通分量的个数 30 if(!far && chd>1 || far && low[i]>=dfn[x] ) //能让x成为割点的孩子i 31 { 32 33 34 sum++; 35 iscut[x]=1; 36 if(iscut[i]||f) cnt++; //这个孩子是割点或者满足单点单边条件 37 } 38 } 39 else if(i!=far) 40 low[x]=min(low[x], dfn[i]); 41 } 42 if(!far && iscut[x]) 43 { 44 iscut[x]=cnt; //根节点 45 if(sum>cnt) iscut[x]++; 46 } 47 if( far && iscut[x]) //非根节点 48 { 49 if(!cnt ) iscut[x]=2; //没有“是割点”的孩子，那么只要自己是割点，起码可以割为两个连通分量 50 else if(sum==cnt) iscut[x]=cnt+1; //有“是割点”的孩子，那么每个“割点”孩子是1个连通分量，注：有可能还有非割点孩，他们算1个连通分量 51 else iscut[x]=cnt+2; 52 } 53 if(iscut[x]) flag=1; //无割点的标记' 54 //if(x==1) cout<<"**"< <