学步园

        题目大意是一个公司有一个网络，连接着从编号1到N共N个地方，然后给出一些边，表示哪两个地方相连。有些点一旦断开所有和它关联的边，那么图不再联通，称这样的点为“critical  place”，求有多少个这样的点。

/* DFS求割点，在DFS时记录每个节点的深度dep和它的子孙所能达到的最浅位置low
 * 1)如果u根节点儿子大于1个，根节点为割点
 * 2)如果u不是根节点且对于u的子孙v有low[v]>=dep[u]，u为一个割点
 * 注意输入和输出(输入用getchar() != '/n' 来控制一行 )
 */

#include <cstdio><br /> #include <cstring><br /> #define M 102<br /> using namespace std;<br /> int map[M][M],low[M],dep[M];<br /> int f[M],n,depth,root;<br /> bool flag[M];<br /> int min(int a,int b){<br /> return a<b?a:b;<br /> }<br /> void dfs(int m){<br /> dep[m] = depth;<br /> low[m] = depth;<br /> depth++;<br /> flag[m] = true;<br /> int i,j,k;<br /> for(i = 1;i <= n; i++){<br /> if(map[m][i]){<br /> if(!flag[i]){<br /> dfs(i);<br /> low[m] = min(low[m],low[i]);<br /> if(low[i] >= dep[m] && m != 1)<br /> f[m] ++; //if low[i] >= dep[m]且m不是根节点，m是割点<br /> else if(m == 1) root ++;<br /> }<br /> else //有后向边<br /> low[m] = min(low[m],dep[i]);<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int i,j,k;<br /> while(scanf("%d",&n),n){<br /> memset(map,0,sizeof(map));<br /> memset(f,0,sizeof(f));<br /> memset(low,0,sizeof(low));<br /> memset(flag,false,sizeof(flag));<br /> memset(dep,0,sizeof(dep));<br /> root = 0;<br /> while(scanf("%d",&k),k){<br /> while(getchar() != '/n'){<br /> scanf("%d",&j);<br /> map[k][j] = map[j][k] = 1;<br /> }<br /> }<br /> root = 0;<br /> depth = 1;<br /> dfs(1);<br /> int ans = 0;<br /> if(root > 1) ans ++;<br /> for(i = 2;i <= n; i++)<br /> if(f[i]) ans ++;<br /> printf("%d/n",ans);<br /> }<br /> }