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 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 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
無向連通圖的割點(diǎn)性質(zhì)
1. 考慮根節(jié)點(diǎn)root。如果頂點(diǎn)x和y同是root的兒子，那么由此證明x無法通過非root的頂點(diǎn)與y相連，所以當(dāng)根root有數(shù)量>1的兒子時(shí)，根是圖的割點(diǎn)。
2. 考慮非根節(jié)點(diǎn)i，再考慮i的某個(gè)兒子節(jié)點(diǎn)j。易知：
和j相連的白色節(jié)點(diǎn)都將成為j的子孫。
和j相連的灰色節(jié)點(diǎn)都是j的祖先，由j指向i祖先的邊稱為后向邊。
黑色節(jié)點(diǎn)不可能與j相連。
如果j和j的子孫都不存在指向j的祖先的后向邊，那么刪除頂點(diǎn)i后，頂點(diǎn)j和i的祖先或者兄弟無法連通。因此，當(dāng)且僅當(dāng)i的某個(gè)兒子及兒子的子孫均沒有指向i祖先的后向邊時(shí)，i是圖的割點(diǎn)。
割點(diǎn)的算法
在dfs的基礎(chǔ)上增加ancestor數(shù)組，ancestor[k]記錄與k及k的子孫相連的輩分最高的祖先所在的深度，當(dāng)ancestor[j]>=deep[j](j是i的兒子)時(shí)j和j的子孫不存在指向i祖先的后向邊，則i是割點(diǎn)。Son表示頂點(diǎn)k的兒子的數(shù)量。根節(jié)點(diǎn)和非根節(jié)點(diǎn)要區(qū)別對待。
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 110;
vector< vector<int> > adj;
int cut[MAXN],mark[MAXN],deep[MAXN],ancestor[MAXN];
char *read(char str[],char *p)
{
while(*p && *p!=' ') p++;
while(*p && *p==' ') p++;
return p;
}
void dfs(int u,int father,int depth){
int i,v,son=0;
mark[u]=1;
deep[u]=ancestor[u]=depth;
for(i=0;i<adj[u].size();i++){
v=adj[u][i];
if(v!=father && mark[v]==1)
ancestor[u]=min(ancestor[u],deep[v]);
if(mark[v]==0){
dfs(v,u,depth+1);
son=son+1;
ancestor[u]=min(ancestor[u],ancestor[v]);
if((father==-1 && son>1) || (father!=-1 && ancestor[v]>=deep[u]))
cut[u]=1;
}
}
mark[u]=2;
}
int main(){
int i,x,y,n,cnt;
char str[MAXN*10],*p;
while(scanf("%d",&n),n){
adj.assign(n,vector<int>());
while(scanf("%d",&x),x){
gets(str);
for(p=read(str,str);sscanf(p,"%d",&y)!=EOF;p=read(str,p))
adj[x-1].push_back(y-1),adj[y-1].push_back(x-1);
}
memset(cut,0,sizeof(cut));
memset(mark,0,sizeof(mark));
for(i=0;i<n;i++)
if(!mark[i]) dfs(i,-1,0);
for(cnt=i=0;i<n;i++)
if(cut[i]) cnt++;
printf("%d\n",cnt);
}
return 0;
}