J. Serval and essay (tarjan finds topological order)

nature ：tarjan Every time push_back(s[tp]) Then we can get the reverse topological order without shrinking points .

Portal ：J.Serval and Essay

The question ： Here's a picture for you , You can select any starting point st(st In degree can not be 0). from u arrive v after ,u Will be deleted .u Able to reach v If and only if v The degree of entry is 1( arrive v after v The degree of entry is 0), Ask how many points you can reach at most .

analysis ： Not all in a ring can be taken , No way to shrink . consider tarjan Enumerate the starting point after finding the topological order .

Code ：

#include<bits/stdc++.h>
using namespace std;
#define int long long
// #define int __int128
#define pii pair<int,int>
#define endl '\n'// Interactive questions need endl Refresh //
const int maxn=1e6+5;
vector<int>e[maxn];
int x[maxn],y[maxn];

int dfn[maxn],low[maxn],s[maxn],instk[maxn],tp;
int scc[maxn],sc;// node i Where scc Number 
int sz[maxn];//scc size 
int dfncnt;

int ind[maxn];
int vis[maxn];

int ct;

vector<int>ord;

void tarjan(int u)
{
    low[u]=dfn[u]=++dfncnt,s[++tp]=u,instk[u]=1;
    for(auto v:e[u])
    {
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instk[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        ++sc;
        while(1)
        {
            scc[s[tp]]=sc;
            sz[sc]++;
            ord.push_back(s[tp]);// Record the reverse topological order of non shrinking points 
            instk[s[tp]]=0;
            --tp;
            if(s[tp+1]==u) break;
        }
    }
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) e[i].clear(),sz[i]=dfn[i]=ind[i]=vis[i]=0;
    dfncnt=sc=tp=0;
    ord.clear();

    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int x;
            cin>>x;
            e[x].push_back(i);
            ind[i]++;
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i);
    }

    reverse(ord.begin(),ord.end());// After flipping, it is a topological order without shrinking points 

    int maxx=0;
    for(auto st:ord)// Enumeration starting point 
    {
        if(vis[st]) continue;
        vector<int>q{st},ops;
        for(int i=0;i<q.size();i++)// Each recalculation q.size(), And auto Different 
        {
            int u=q[i];
            vis[u]=1;
            for(auto v:e[u]) 
            {
                if(v==st) continue;// Ring 
                ops.push_back(v);
                if(--ind[v]==0) q.push_back(v);
            }
        }
        maxx=max(maxx,(int)q.size());// from st set out , At most q.size() Point penetration is 0（ You count st）
        for(auto v:ops) ind[v]++;
    }
    printf("Case #%lld: %lld\n",++ct,maxx);
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}