最小支配集，最大獨立集，最小點覆蓋參考博客https://www.cnblogs.com/Ash-ly/p/5775934.html?

最小支配集：選出一些點讓這些點與剩下的點都有邊且選出的點最少

首先我們先深度優先搜素一下將所有點標記一下順序然后我們將點的父親標記記錄一下

最后反向貪心選擇點，如果這個點沒有被標記，我們就將他父親加進點集里面標記這個點 ，父節點，父節點的父節點（至于為什么反向貪心，因為從最后一個點開始基本都有父親從前面開始有些店沒有父親）；

練習題：?https://ac.nowcoder.com/acm/contest/1069/A

代碼實現如下

#include <bits/stdc++.h>typedef long long ll; typedef long long ld;using namespace std;const ll maxn = 1e5 + 7;ll pre[maxn],dfn[maxn]; bool flag[maxn],flag1[maxn]; vector<ll>mp[maxn]; ll cnt; void dfs(ll x) {dfn[++cnt] = x; for(int i = 0; i < mp[x].size(); i ++){ll to = mp[x][i];if(!flag[to]){pre[to] = x;flag[to] = 1;dfs(to);}} }vector<ll> b; int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin >> n;for(int i = 1; i <= n - 1; i ++){ll x,y;cin >> x >> y;mp[x].push_back(y);mp[y].push_back(x);}flag[1] = 1;dfs(1);ll ans = 0;memset(flag,0,sizeof(flag));for(int i = cnt; i >= 1; i --){if(!flag[dfn[i]]){if(!flag1[pre[dfn[i]]]){flag1[pre[dfn[i]]] = 1;ans ++; }flag[dfn[i]] = 1;flag[pre[dfn[i]]] = 1;flag[pre[pre[dfn[i]]]] = 1;}}cout << ans << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的最小支配集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。