学步园

标准的求割顶的问题，用tarjan算法，参见www.nocow.cn割点词条

/*
 * poj1144 AC
 * 求无向图割顶
 * tarjan算法，好好背一背！
 * */
#include<memory.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct NODE{
	int v,next;
}edge[20020];
long tot,head[105];
int n,ans,dfn[105],low[105],sons,ind;

int tarjan(int x)
{
	int i;
	bool mark = false;
	dfn[x] = low[x] = ++ind;
	i = head[x];
	while(i)
	{
		if(!dfn[edge[i].v])
		{
			if(x==1) sons++;
			tarjan(edge[i].v);
			low[x] = min(low[x],low[edge[i].v]);
			if(x!=1 && low[edge[i].v]>=dfn[x])       /*这个判断一定在这个if语句中！！要判断x是否等于1*/
				mark = true;
		}else
			low[x] = min(low[x],dfn[edge[i].v]);
		
		i = edge[i].next;
	}
	if(mark) ans++;
	return ans;
}

int main()
{
//	FILE* fin;
	int j,k;
	char c;
//	fin = fopen("d.in","r");
	while(scanf("%d",&n) && n)
	{
		memset(edge,0,sizeof(edge));
		memset(head,0,sizeof(head));
		tot = sons = ans = ind = 0;
		while(scanf("%d",&j) && j)
		{
			while((c=getchar())!='\n')
			{
				scanf("%d",&k);
				edge[++tot].v = k;
				edge[tot].next = head[j];
				head[j] = tot;
				edge[++tot].v = j;
				edge[tot].next = head[k];
				head[k] = tot;
			}
		}
		int sum = 0;
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		sum = tarjan(1);

		if(sons>1) sum++;
		printf("%d\n",sum);
	}
	return 0;
}