题目大意：求以无向图割点。
定义：在一个连通图中，如果把点v去掉，该连通图便分成了几个部分，则v是该连通图的割点。
求法：如果v是割点，如果u不是根节点，则u后接的边中存在割边（u，v），或者v->Low所对应的节点就是u（即u->DfsN <= v->Low)，图所分成的部分为v的子树与其它；如果u是根节点，则如果搜索树中与u相连的边数大于等于2，图被分成的部分为各个与根相连的子树。
特判：
- 求割边时需要考虑通往父亲的边，但是求割点就算有再多的重边也不会有影响。
- 所以只需特判根节点。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int MAX_NODE = 100, MAX_EDGE = 10010; struct Node;
struct Edge; struct Node
{
int Id, DfsN, Low;
bool IsCut;
Edge *Head;
}_nodes[MAX_NODE], *Root;
int _vCount, DfsCnt; struct Edge
{
Node *From, *To;
Edge *Next;
Edge() {}
}*_edges[MAX_EDGE];
int _eCount; void Init(int vCount)
{
_vCount = vCount;
_eCount = 0;
DfsCnt = 0;
memset(_nodes, 0, sizeof(_nodes));
} Edge *NewEdge()
{
_eCount++;
return _edges[_eCount] ? _edges[_eCount] : _edges[_eCount] = new Edge();
} Edge *AddEdge(Node *from, Node *to)
{
Edge *e = NewEdge();
e->From = from;
e->To = to;
e->Next = from->Head;
from->Head = e;
return e;
} void Build(int uId, int vId)
{
Node *u = uId + _nodes, *v = vId + _nodes;
u->Id = uId;
v->Id = vId;
Edge *e1 = AddEdge(u, v), *e2 = AddEdge(v, u);
} void Dfs(Node *u)
{
if (u->DfsN)
return;
u->DfsN = u->Low = ++DfsCnt;
int cnt = 0;
for (Edge *e = u->Head; e; e = e->Next)
{
if (!e->To->DfsN)
{
cnt++;
Dfs(e->To);
u->Low = min(u->Low, e->To->Low);
if (u->DfsN <= e->To->Low && (u != Root || cnt > 1))
u->IsCut = true;
}
else
u->Low = min(u->Low, e->To->DfsN);
}
} int GetCutCnt()
{
for (int i = 1; i <= _vCount; i++)
{
Root = i + _nodes;
Dfs(_nodes + i);
}
int ans = 0;
for (int i = 1; i <= _vCount; i++)
if (_nodes[i].IsCut)
ans++;
return ans;
} int main()
{
#ifdef _DEBUG
freopen("c:\\noi\\source\\input.txt", "r", stdin);
#endif
int totNode, uId, vId;
char s[110];
while (~scanf("%d\n",&totNode) && totNode)
{
Init(totNode);
while (cin.getline(s,sizeof(s)) && s[0] != '0')
{
int uId, vId, p = 0, res;
sscanf(s, "%d", &res);
uId = res;
while (res)
{
p++;
res /= 10;
}
p++;
while (s[p])
{
sscanf(s + p, "%d", &vId);
Build(uId, vId);
while (vId)
{
p++;
vId /= 10;
}
if (!s[p])
break;
p++;
}
}
int ans = GetCutCnt();
printf("%d\n", ans);
}
return 0;
}