Cod sursa(job #2780202)

Utilizator bubblegumixUdrea Robert bubblegumix Data 6 octombrie 2021 14:36:10
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#pragma GCC optimize("Ofast,unroll-loops") 
#pragma GCC target("avx,avx2,fma") 
#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<vector>
#include<climits> 
#define rep(i,a,b) for (int i = a; i <= b; i++) 
#define repd(i,a,b) for (int i = a; i >= b; i--)
#define feach(it,v) for(auto& it : v)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define hmap unordered_map 
#define hset unordered_set
#define inf 0x3f3f3f3f
#define inrange(x,a,b) (x>=a && x<=b)
#define nmax 2*100005
using namespace std;
typedef long long ll;
int t;
vector<int> g[nmax];
bool viz[nmax], instack[nmax];
int n;
int cyc;
int ans;
int dp[nmax];
void dfs(int i)
{
	viz[i] = instack[i] = 1;
	feach(it, g[i])
		if (!viz[it])
		{
			dfs(it);
			int add = (i < it) ? 1 : 0;
			dp[i] = max(dp[i], dp[it] + (i < it));
			ans = max(ans, dp[i]);
		}
		else
			if (instack[it])
				cyc = 1;
	instack[i] = 0;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n;
		cyc = ans = 0;
		rep(i, 1, n)
		{
			g[i].clear();
			viz[i] = instack[i] = dp[i] = 0;
		}
		rep(i, 1, n)
		{
			int k;
			cin >> k;
			while (k--) {
				int x;
				cin >> x;
				g[i].push_back(x);
			}
		}
		rep(i, 1, n)
			if (!viz[i])
				dfs(i);
		if (cyc) {
			cout << -1 << '\n';
			continue;
		}
		else
			cout << ans + 1 << '\n';

	}
}