题解：CF2044G2 Medium Demon Problem (hard version)

· · 题解

拓扑排序加一点点树结构。

首先是思路。

事实上，无论这个环到底是什么样子、到底有几个，想要有解，环上所有结点的玩具数就必须相等。也就是说，从出题数据确定的那一刻开始，环的结局就已经确定了。所以我们只需要考虑环外的结点即可。

可以通过拓扑排序找到所有的环外结点。可以确定的是，因为它们在环外，它们肯定会呈现出一个或多个树形图结构。我们要做的，就是将这些树的根结点找出来一一比较，玩具最多的那个根结点，就是我们需要的答案。

请注意，根结点的玩具数等于所有子树的和加上本身初始状态的一，也就是这棵树的玩具总数。

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
//对应数组分别为：路径、入度、礼物个数
int T, N, arr[200010], f[200010], sum[200010], S, n, temp, ans;
vector<int>V;//存储非环结点
queue<int>Q;//筛选非环结点
//4 1 1 5 4
int main()
{
    std::ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> N;
        ans = 0; 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            f[arr[i]]++, sum[i] = 1;//入度、玩具初始化
        }

        for (int i = 1; i <= N; i++) {
            if (f[i] == 0)Q.push(i),V.push_back(i);//第一批入度为零的结点入队，同时也是非环结点
        }
        while (!Q.empty()) {//拓扑排序，挑选所有非环结点
            temp = Q.front();
            Q.pop();
            f[arr[temp]]--;
            if (f[arr[temp]] == 0)Q.push(arr[temp]),V.push_back(arr[temp]);
        }

        for (auto t : V) {//将所有非环结点的玩具数分发下去
            sum[arr[t]] += sum[t];
        }
        for (auto t : V) {//统计拥有最多玩具的结点
            ans=max(ans,sum[t]);
        }

        //善后工作
        V.clear();
        for (int i = 1; i <= N; i++) {
            arr[i] = 0, f[i] = 0, sum[i] = 0;
        }
        cout << ans+2 << '\n';//从第二年开始，记得加2
    }
    return 0;
}