2022牛客暑期多校训练营1 J Serval and Essay

题意：
给一个图，对于图内的每个点，当且仅当其所有入边入应的点为真时，该点为真。开始可指定一个点为真，问为真的点的最大个数
思路：
有可能使结果最大的起始点
1.当一个点V1的父节点V2只有一个时，选父节点V2作为起始点,若V2的父节点V3只有一个时，则选V3，直到某个节点父节点多于一个或为0，将其设置为起始点
2.当存在环时，选环上的任意一点作为起始点
对于所有满足条件的点，模拟一遍拓扑排序，取最大值作为结果，可以证明每个点遍历次数不超过10次，故复杂度可控制在1e8内

Code

#include <bits/stdc++.h>
// #define debug freopen("_in.txt", "r", stdin);
#define debug freopen("_in.txt", "r", stdin), freopen("_out.txt", "w", stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef struct Node *bintree;
using namespace std;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll maxn = 1e6 + 10;
const ll maxm = 2e6 + 10;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-8;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

ll T, n, m, q, d,kase=0;
string str, str1;
vector<ll> to[maxn], vec;
map<ll, ll> mp;
ll fa[maxn], tag[maxn], ind[maxn], tmp[maxn];
queue<ll> que, que1;

void solve()
{
    
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
    {
    
        to[i].clear();
        tag[i]=0;
    }

    while (!que.empty())
    {
    
        que.pop();
    }
    
    for (ll i = 1; i <= n; i++)
    {
    
        scanf("%lld", &m);
        ind[i] = m;
        for (ll j = 1; j <= m; j++)
        {
    
            ll x;
            scanf("%lld", &x);
            fa[i] = x;
            to[x].push_back(i);
        }
        if (m == 1)
        {
    
            tag[fa[i]] = 1;
            que.push(fa[i]);
        }
        else
        {
    
            fa[i] = 0;
        }
    }
    for (ll i = 1; i <= n; i++)
    {
    
        tmp[i] = ind[i];
    }
    ll ans = 1;
    while (!que.empty())
    {
    
        ll temp = que.front();
        que.pop();
        if (!tag[temp])
            continue;
        tag[temp] = 0;
        ll now = temp;
        while (tag[fa[temp]] > 0)
        {
    
            if (fa[temp] == now)
            {
    
                break;
            }

            temp = fa[temp];
            tag[temp] = 0;
        }
        vec.clear();
        mp.clear();
        while (!que1.empty())
            que1.pop();
        que1.push(temp);
        vec.push_back(temp);
        mp[temp] = 1;
        tmp[temp] = 0;
        ll res = 1;
        while (!que1.empty())
        {
    
            ll x = que1.front();
            que1.pop();

            for (auto y : to[x])
            {
    
                if (mp[y] == 0)
                {
    
                    mp[y] = 1;
                    vec.push_back(y);
                }
                tmp[y]--;
                if (tmp[y] == 0)
                {
    
                    que1.push(y);
                    res++;
                    tag[y] = 0;
                }
            }
        }
        ans = max(ans, res);
        for (auto x : vec)
        {
    
            tmp[x] = ind[x];
        }
    }

    printf("Case #%lld: %lld\n",++kase, ans);
}

signed main()
{
    
    // debug;
    scanf("%lld", &T);
    // T = 1;
    while (T--)
    {
    
        solve();
    }
}