1572A - Book - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vb vector<bool>
#define get(a)        \
    for (auto &i : a) \
    cin >> i
#define put(a)        \
    for (auto &i : a) \
    cout << i << " "
#define endl "\n"
#define sp << " " <<
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const int N = 1e6 + 2;
const int mod = 1e9 + 7;
const int INF = LLONG_MAX;
using namespace std;
int vis[N];
int bvis[N];
int dist[N];

const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];
int dp[N];

bool dfs(int vertex,vector<pair<int,int>> graph[]){
    vis[vertex]=1;
    bvis[vertex]=1;
    for(auto child:graph[vertex]){
        if(vis[child.first]!=1){
            if(dfs(child.first,graph)){
                return true;
            }

        }
            
        else if(bvis[child.first]==1){
                return true;
            }
    }
    bvis[vertex]=0;
    return false;
}
int dfs1(int u,vector<pair<int,int>> graph[]) {
    if (dp[u] != -1) return dp[u]; // memoization
    dp[u] = 0;
    for (auto p : graph[u]) {
        int v = p.first, w = p.second;
        dp[u] = max(dp[u], dfs1(v,graph) + w);
    }
    return dp[u];
}

int longestPath(vector<pair<int,int>> graph[],int n) {
    
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int u = 1; u <= n; u++) {
        if (dp[u] == -1) dfs1(u,graph);
        ans = max(ans, dp[u]);
    }
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<pair<int,int>> graph[n+1];
        vector<int> graph1[n+1];
        for(int i=1;i<=n;i++){
            vis[i]=0;
            bvis[i]=0;
            dist[i]=0;
        }
        set<int> s;
        for(int i=1;i<=n;i++){
            int x;cin>>x;
            for(int j=0;j<x;j++){
                int y;cin>>y;
                if(i>y){
                    graph[i].push_back({y,0});
                }
                else{
                    graph[i].push_back({y,1});

                }
                
            }
            if(x==0){
                s.insert(i);
            }
            
        }
        bool q=false;
        for(int i=1;i<=n;i++){
            if(vis[i]==1)continue;
            if(dfs(i,graph)){
                cout<<-1<<endl;
                q=true;
                break;
            }
        }
        if(q){
            continue;
        }
        for(int i=1;i<=n;i++){
            dp[i]=-1;
        }
        int ans=longestPath(graph,n);
        cout<<ans+1<<endl;
        
     
    }

    return 0;
}