【題目描述】

A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is
possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure
occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them. 

Input

The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated
by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0; 

Output

The output contains for each block except the last in the input file one line containing the number of critical places. 

Sample Input

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0

Sample Output

1
2

【題目分析】
題目要求求割點，首先什么是割點呢？就是一個連通圖/連通分量中將這個點去掉就不再是一個連通圖的點。
我們想要求割點，很顯然可以直接暴力，先在一個連通圖里面刪去這個點所有的邊，如果變得不連通了就是割點。可是這樣時間復雜度顯然是不允許的。
我們再來仔細觀察割點有什么特點：刪去這個點就有一些點無法到達。
我們結合Trajan算法中的DFS搜索樹進行分析，如果一個點是割點，如果他后面的子樹就無法訪問到前面的點，那么刪去這個點，前面的點也就無法訪問后面的點了，前后兩部分無法相互訪問，那說明這個點就是一個割點。我們如何判斷后面的子樹不會訪問到前面的點呢？我們可以用Trajan算法中的LOW數組 ，如果子樹的LOW數組的值比這個點的DFN的值還大說明這個點就是一個割點。
可是對于根節點（開始訪問的點）來講，就算這個點是一個割點后面的點也不會訪問到他前面的點，但是這個根節點不同搜索樹上的點是互相沒有關系的，如果他有兩個或者兩個以上的搜索樹，那么刪去根節點也可以形成割點。但是對于一般的點，就算他有好幾個兒子節點也不一定是一個割點，因為這些兒子之中有可能有之前訪問過的點，但是對于訪問過的點我們是不會放入這個搜索樹的，所以不同搜索樹有可能訪問到同一個之前的點，這樣就算刪去這個點也可能有通路。但是對于根節點就無法訪問到更前面的點了，所以就可以確定是一個割點。

總結一下，割點總共就兩類：

1. 含有兩個或者兩個以上子樹的根節點u $(u==root$ && $son>1)$
2. 子樹節點v的搜索樹中不含有祖先節點的點u$(u!=root$ && $LOW[v]>=DFN[u])$

【AC代碼】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int MAXN=105;
const int MAXM=MAXN*MAXN;
struct node
{int v,next;
}Edge[MAXM];
int head[MAXN],tot;
int DFN[MAXN],LOW[MAXN];
bool cnt[MAXN];
int vis[MAXN],Time;
int n,root,ans;void init()
{memset(head,0,sizeof(head));tot=0;memset(vis,0,sizeof(vis));Time=0;memset(cnt,0,sizeof(cnt));
}void AddEdge(int u,int v)
{tot++;Edge[tot].v=v; Edge[tot].next=head[u];head[u]=tot;
}void read()
{int u,v;while(~scanf("%d",&u) && u){while(getchar()!='\n'){scanf("%d",&v);AddEdge(u,v); AddEdge(v,u);}}
}void Trajan(int x,int fa)
{int v;int son=0;DFN[x]=LOW[x]=++Time;vis[x]=1;for(int i=head[x];i;i=Edge[i].next){v=Edge[i].v;if(vis[v]==0){Trajan(v,x);son++;LOW[x]=min(LOW[x],LOW[v]);if(x==root &&son>1 || x!=root && LOW[v]>=DFN[x]){cnt[x]=true;}}else if(vis[v]==1){LOW[x]=min(LOW[x],DFN[v]);}}vis[x]==2;	//說明這個搜索數完結了和其他的點就沒有什么關系了，因此設為2其他點就不會訪問到
}void solve()
{ans=0;root=1;for(int i=1;i<=n;i++){if(!vis[i]){root=i;Trajan(i,i);}}for(int i=1;i<=n;i++){if(cnt[i]) ans++;}printf("%d\n",ans);
}int main()
{while(~scanf("%d",&n) && n){init();read();solve();}return 0;
}