【图论模型的建立】
　　本题的数学模型在题目中已明示，我们将其用数学语言重述一遍：在图G=(V,E)中找一顶点集S，使得对任意(u,v)∈E有u∈S或v∈S，且|S|最小。很明显，这是求图的最小顶点覆盖集。
【算法分析】

　　图的最小顶点覆盖是NP问题，至今还没有有效算法。而本题N的规模可达1500，显然用搜索是无法完成的。但本题的图十分特殊是一棵树。为了进一步利用数据结构的特殊性，我们不妨先手工分析一个例子。左图为一个有13个顶点的树，其中用红色圈出的顶点为找到的最小覆盖集。很明显，叶节点不可能属于覆盖集，但叶节点的父节点一定属于覆盖集，以此为基础再判断上一层次节点是否属于覆盖集。左图的节点编号从大到小正好是我们判断的顺序，该顺序恰好是树的前序遍历顺序，由此我们可得出本题的算法：

　　1：procedure Min-Vertex-Cover(T);
　　2：begin
　　3： 　按前序遍历顺序重新编排整棵树的节点编号。
　　4： 　for I:=1 to n do cover[I]:=0;
　　5： 　for I:=n Downto 2 do
　　6： 　　if (cover[I]=0) and (cover[parent[I]]=0) then
　　7： 　　　　cover[parent[I]]:=1;
　　8：end;
　　
　　该算法是一个贪心算法。算法中用数组cover来标记选入覆盖点集的树结点，即当结点i被选入覆盖点集，则cover[i]=1，否则cover[i]=0。为了说明算法的正确性，必须证明关于树的最小顶点覆盖问题满足贪心选择性质并且具有最优子结构性质。具体的证明过程，在《若干NP完全问题的特殊情形》一文中已有详细的叙述。
　　最后我们分析一下算法的复杂度，前序遍历树显然可以在O(n)时间内完成，再加上for循环显然需要O(n)的时间，从而整个算法所需的时间为O(n)。对于本题的规模，完全可以接受了。
【小结】
　　本题的数学模型是一个NP问题，然而在树这样一个特殊结构下，我们充分利用题目中的已知信息，降低了题目的难度，找到了线性时间的算法。通过解这道题我认识到充分利用题目信息的重要性，一个算法越体现出题目的特征，效率也就越高，当然它的适用范围也就越狭窄，这也正是构造法解题之所以高效的原因。
【参考文献】
《若干NP完全问题的特殊情形》 《福州大学学报》99.5 王晓东
【附录】
源程序：Strategi.pas

Program exp;
Var count,m,tmp,k,j,i,n:Integer;
　　Convert,Parent,Cover:Array [0..1500] Of Integer; {Convert[I]：节点I的前序遍历标号； 　　　　　Parent[I]：指出节点I的父亲节点；Cover[I]：是否覆盖节点[I]}
Procedure Preorder(root:Integer); {树的前序遍历、标号过程}
Var i,j,k:Integer;
Begin
　Convert[count]:=root;Inc(count);
　For i:=1 To n Do
　　If Parent[i]=root Then Preorder(i);
End;
Begin
　Assign(input,'input.txt');Reset(input);
　Assign(output,'output.txt');Rewrite(output);
　{初始化并读入数据}
　Readln(n);
　For i:=0 To n Do parent[i]:=-1;
　For i:=1 To n Do Begin
　　Read(j,m);
　　For k:=1 To m Do Begin
　　　Read(tmp);Parent[tmp]:=j;
　　End;
　　Readln;
　End;
　Fillchar(cover,sizeof(cover),0);
　count:=1;i:=-1;Repeat Inc(i) Until Parent[i]=-1;
　Preorder(i);count:=0;
　For i:=n Downto 2 Do {贪心算法}
　　If (cover[Convert[i]]=0) and (Cover[parent[Convert[i]]]=0) Then Begin
　　　　cover[parent[Convert[i]]]:=1;
　　　　Inc(count);
　　End;
　Writeln(count);
　Close(output);
End.