2022 Nioke Summer Multi-School Training Camp 1 J Serval and Essay

题意：
给一个图,for each point in the graph,if and only if all of its incoming edges are true,This point is true.Start can specify a point to be true,Ask the maximum number of true points
思路：
A starting point that is likely to maximize the result
1.当一个点V1的父节点V2只有一个时,select parent nodeV2作为起始点,若V2的父节点V3只有一个时,则选V3,Until a node has more than one parent or is0,Set it as the starting point
2.当存在环时,Pick any point on the ring as the starting point
for all points that satisfy the condition,Simulate a topological sort,Take the maximum value as the result,It can be proved that each point is traversed no more than 10次,So the complexity can be controlled at1e8内

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();
    }
}