创世纪

题目概述

上帝手中有 $N \le 10^5$ 种世界元素，每种元素可以限制另外 $1$ 种元素，把第 $i$ 种世界元素能够限制的那种世界元素记为 $A[i]$。

现在，上帝要把它们中的一部分投放到一个新的空间中去建造世界。

为了世界的和平与安宁，上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素限制它。

上帝希望知道，在此前提下，他最多可以投放多少种世界元素？

感觉网上的贪心题解都稍有问题？

单纯考虑一个树（不是基环树），发现可直接从子节点贪心得出父节点状态

首先，这是一个内向树森林

考虑一颗内向基环树 $T$，环上节点为 $s_1, s_2, \cdots,s_t$

对每一个环上节点和其子树分开执行贪心（这只是描述，实际上用拓扑排序递推）

1. 如果 $T$ 是一个环，则 $t/2$
2. 如果存在一个 $s_i$ 由贪心过程得出它可以投放，则环就会断成链
3. 如果不存在，则环还是完整的，$t/2$

贪心过程由拓扑排序执行，讨论 2 可以直接在这个过程中完成

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;
const int N = 1000010;

int n, a[N], deg[N], q[N], l, r, vis[N];

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    cin >> n;
    rep(i, 1, n) {
        cin >> a[i];
        deg[a[i]]++;
    }
    l = 1, r = 0;
    rep(i, 1, n) if (deg[i] == 0) q[++r] = i;
    int ans = 0;
    while (l <= r) {
        int u = q[l++], v = a[u];
        if (!vis[u] && !vis[a[u]]) {
            vis[v] = 1;
            ans++;
            deg[a[a[u]]]--;
            if (deg[a[a[u]]] == 0) q[++r] = a[a[u]];
        }
        vis[u] = 1;
    }
    rep(i, 1, n) {
        if (!vis[i]) {
            int u = i;
            int cnt = 0;
            do {
                vis[u] = 1, cnt++, u = a[u];
            } while (u != i);
            ans += cnt / 2;
        }
    }
    cout << ans << endl;
    return 0;
}