Solution Of P11501 [ROIR 2019 Day 2] 探险队

· · 题解

Solution

之前写的由于表述方式不好讲的不清楚，改了一下。

提供一种很好写的做法。

首先我们注意到一共有 n 条关系，因此这构成基环树森林。

这个问题就等价于求最大独立集，然后这在基环树上是可以贪心的。

我们不妨令 a_i 为 i 的父亲。那么我们从叶子节点开始取，然后再间隔着取，这样一定不劣（即，按照拓扑序取）。然后为了方便统计，每次直接删掉处理过的点和边。

经过上述处理，基环树就只剩下一个环了，我们再在环上贪心染一遍色就好了。

搜索的时候记录答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 3e5 + 3;
int n, a[N], in[N], ans;
bool vis[N];
void dfs (int u, int w) {
    if (vis[u]) return;
    vis[u] = true; ans += w;
    if (a[u] == -1) return;
    if (-- in[a[u]] == 0 || w == 1) dfs (a[u], w ^ 1);
}
int main() {
    cin.tie(NULL) -> sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], (~a[i]) ? in[a[i]] ++ : 0;
    for (int i = 1; i <= n; i ++) if (!in[i]) dfs(i, 1);
    for (int i = 1; i <= n; i ++) if (!vis[i]) dfs(i, 0);
    cout << ans << '\n';
    return 0;
}