最小支配集：指从所有顶点中取尽量少的点组成一个集合，使得剩下的所有点都与取出来的点有边相连。顶点个数最小的支配集被称为最小支配集。这里用贪心法来求。
1.以1号点深度优先搜索整棵树，求出每个点在DFS中的编号和每个点的父亲节点编号。 2.按DFS的反向序列检查，如果当前点既不属于支配集也不与支配集中的点相连，且它的父亲也不属于支配集，将其父亲点加入支配集，支配集个数加1。 3.标记当前结点、当前结点的父节点(属于支配集)、当前结点的父节点的父节点(与支配集中的点相连)。
;const int MAXN = 20020;struct EdgeNode{int to;int next;}Edges[MAXN];int Head[MAXN],father[MAXN],NewPos[MAXN];bool vis[MAXN];N,M,now;void DFS(int x) //得到深度优先队列的反向序列{NewPos[now++] = x;for(int k = Head[x]; k != -1; k = Edges[k].next){if(!vis[Edges[k].to]){vis[Edges[k].to] = true;father[Edges[k].to] = x;DFS(Edges[k].to);}}}S[MAXN],Set[MAXN];int Greedy()//贪心求最小支配集{memset(S,0,sizeof(S));memset(Set,0,sizeof(Set));int ans = 0;for(int i = N-1; i >= 1; i–)//反向序列检查{int t = NewPos[i];if(!S[t])//当前点未被覆盖，也就是当前点既不属于支配集，也不与支配集中的点相连{if(!Set[father[t]])//当前点的父亲结点不属于支配集，{Set[father[t]] = true; //将父节点加入支配集ans++;//顶点个数加1}S[t] = true;S[father[t]] = true;S[father[father[t]]] = true;//标记当前点、当前结点的父节点、当前结点的父节点的父节点}}return ans;}int main(){int u,v;while(~scanf(“%d”,&N)){ //初始化memset(Edges,0,sizeof(Edges));memset(Head,-1,sizeof(Head));memset(father,0,sizeof(father));memset(vis,false,sizeof(vis));memset(NewPos,0,sizeof(NewPos));int id = 0;for(int i = 0; i < N-1; ++i){scanf(“%d%d”,&u,&v);Edges[id].to = v;Edges[id].next = Head[u];Head[u] = id++;Edges[id].to = u;Edges[id].next = Head[v];Head[v] = id++;}now = 0;vis[1] = true;father[1] = 1;DFS(1);printf(“%d\n”,Greedy());}return 0;}
最小点覆盖：指从所有顶点中取尽量少的点组成一个集合，使得集合中所有的边都与取出来的点有边相连。顶点个数最小的覆盖集被称为最小点覆盖。 贪心策略：如果当前点和当前点的父节点都不属于顶点覆盖集合，则将父节点加入到顶点覆盖集合中，并标记当前节点和其父节点都被覆盖。
int Greedy()//贪心求最小点覆盖{memset(S,0,sizeof(S));memset(Set,0,sizeof(Set));int ans = 0;for(int i = N-1; i >= 1; i–)//反向序列检查{int t = NewPos[i];if(!S[t] && !S[father[t]])//当前点和当前点的父节点都不属于顶点覆盖集合{Set[father[t]] = true; //当前点的父节点加入到顶点覆盖集合中ans++;//顶点个数+1S[t] = true;S[father[t]] = true;//标记当前点、当前结点的父节点}}return ans;}
最大独立集：指从所有顶点中取尽量多的点组成一个集合，使得这些点之间没有边相连。顶点个数最多的独立集被称为最大独立集。 贪心策略：如果当前节点没有被覆盖，则将当前节点加入独立集，，并标记当前节点和其父节点都被覆盖。
int Greedy()//贪心求最大独立集{memset(S,0,sizeof(S));memset(Set,0,sizeof(Set));int ans = 0;for(int i = N-1; i >= 1; i–)//反向序列检查{int t = NewPos[i];if(!S[t])//当前点未被覆盖{Set[t] = true; //将当前点加入独立集ans++;//独立集点个数加1S[t] = true;S[father[t]] = true;//标记当前点、当前结点的父节点都被覆盖}}return ans;}
生命太过短暂，今天放弃了明天不一定能得到
