采用链式前向星存储整棵树。整形数组newpos[i]表示深度优先遍历序列的第i个点是哪个点，now表示当前深度优先遍历序列已经有多少个点了。bool形数组visit[ ]用于深度优先遍历的判重，整形pre[i]表示点i的父节点编号, bool型数组s[i]如果为true,表示第i个点被覆盖， bool型数组set[i]如果为true,表示点i属于要求的点的集合。

#include
 
  
usingnamespacestd;
constintmaxn=1000;
intpre[maxn];//存储父节点
boolvisit[maxn];//DFS标记数组
intnewpos[maxn];//遍历序列
intnow;
intn,m;
inthead[maxn];//链式前向星
structNode{intto;intnext;};
Nodeedge[maxn];

voidDFS(intx){
newpos[now  ]=x;//记录遍历序列
for(intk=head[x];k!=-1;k=edge[k].next){
if(!visit[edge[k].to]){
visit[edge[k].to]=true;
pre[edge[k].to]=x;//记录父节点
DFS(edge[k].to);
}
}
}

intMVC(){
bools[maxn]={0};
boolset[maxn]={0};
intans=0;
for(inti=n-1;i>=1;i--){//逆序进行贪心,排除掉其根节点
intt=newpos[i];
if(!s[t]&&!s[pre[t]]){//如果当前节点和其父节点都不属于顶点覆盖集合
set[pre[t]]=true;//把其父节点加入到顶点覆盖集合
ans  ;//集合内顶点个数加1
s[t]=true;//标记当前节点被覆盖
s[pre[t]]=true;//标记其父节点被覆盖
}
}
returnans;
}

intmain(){
/*readGraphmessage*///建图
memset(visit,false,sizeof(visit));//初始化
now=0;
visit[1]=true;
pre[1]=1;
DFS(1);//从第一个根节点开始寻找遍历序列
MDS();
return0;
}