树的最小支配集，最小点覆盖，最大独立集

(DFS+贪心)

DFS

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int fa[maxn], vis[maxn], ord[maxn], tot;
int mm[maxn][maxn];
void dfs(int s){
    ord[tot++] = s;
    for(int i=1; i<=n; i++){
        if(mm[s][i] && !vis[i]){
            vis[s]=1;
            dfs(i);
            fa[i] = s;
        }
    }
}

最小支配集

int st[maxn]={0}, s[maxn]={0}, ans=0;
int greedy(){
    for(int i=n-1; i>=0; i--){
        int t = ord[i];
        if(!s[t]){
            if(!st[fa[t]]){
                st[fa[t]]=1;ans++;
            }
            s[t] = s[fa[t]] = s[fa[fa[t]]]=1;
        }
    }
    return ans;
}

最小点覆盖

int st[maxn]={0}, s[maxn]={0}, ans=0;
int greedy(){
    for(int i=n-1; i>=0; i--){
        int t = ord[i];
        if(!s[t] && !s[fa[t]]){
            ans++;
            st[fa[t]] = s[t] = st[fa[t]] = 1;
        }
    }
    return ans;
}

最大独立集

int st[maxn]={0}, s[maxn]={0}, ans=0;
int greedy(){
    for(int i=n-1; i>=0; i--){
        int t = ord[i];
        if(!s[t]){
            ans++;
            st[t] = s[t] = s[fa[t]] = 1;
        }
    }
    return ans;
}