abc302f

ganking / 2023-09-01 / 原文

abc302f
不是很难，但是还是有点绕

很明显是一个图的模型
但是边数很大
我们只关心每种数最早什么时候能够得到
对于每一种数，我们记录哪些集合包含它，每得到一个新的数，就用它来更新

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define ff(i,a,b) for ((i)=(a);(i)<=(b);(i)++)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")

using namespace std;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int N=2e5+5;
const int inf=1e9;

int d[N],a[N],z;
int n,m;
vector<int> v[N],w[N];
bool vis[N],bz[N];

int q[N],h,t,x,y;
int main() {
	
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	fo(i,1,m) d[i]=inf;
	
	fo(i,1,n) {
		scanf("%d",&a[i]);
		bool flag=0;
		int x;
		fo(j,1,a[i]) {
			scanf("%d",&x);
			v[i].push_back(x);
			if (x==1) flag=1;
			
			w[x].push_back(i);
		}
		if (flag){
			for (int j=0;j<(int)v[i].size();j++) {
				d[v[i][j]]=0;
			}
		}
	}
	
	fo(i,1,m) if (!d[i]) {
		if (!vis[i]) {
			q[++t]=i; 
			vis[i]=1;
		}
	}
	
	while (h<t) {
		x=q[++h];
		for (int i=0;i<(int)w[x].size();i++) {
			y=w[x][i];
			if (bz[y]) continue;
			
			bz[y]=1;
			for (int j=0;j<(int)v[y].size();j++) {
				z=v[y][j];
				if (vis[z]) continue;
				vis[z]=1;
				
				d[z]=d[x]+1;
				q[++t]=z;
			}
		}
	}
	if (d[m]==inf) puts("-1");
	else printf("%d",d[m]);
	
	return 0;
}