【题解】[NOI Online 2022 提高组] 讨论

这题是贪心。

我们按 k 从小到大排序，那么长度大的和长度小的如果有公共元素的话，长度小的一定是长度大的子集。

这样的话，我们对每个值记录找到的最晚的那个人（贪心），然后暴力判断。

我想这道题难倒我的原因在于 数据规模 ，但是如果我们按 关键信息 排序，就会找到解题路径。

这种题目的逻辑链条往往不长，但是 要想到第一步转化 。

那么我们就要积累 做杂题的经验 ，锻炼 破题 的能力。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e6+5;
int T,n,vis[N],pre[N],Rec[N];
vector<int> g[N];
struct node{
          
   
	int k,id;
	bool operator <(const node &a)const {
          
   
		return k<a.k;
	}
}a[N];
bool solve(int x) {
          
   
	Rec[x] = 1;
	for(auto y:g[x]) {
          
   
		if(!vis[y]) {
          
   
			return 1;
		}
	}
	return 0;
}
void check() {
          
   
	for(int i=1;i<=n;i++) {
          
   
		int x=a[i].id;
		if(!g[x].size()) continue;
		for(auto y:g[x]) {
          
   
			vis[y]=1;
		}
		for(auto y:g[x]) {
          
   
			int tmp=pre[y];
			if(tmp && !Rec[tmp] && solve(tmp)) {
          
   
				printf("YES
");
				printf("%d %d
",tmp,x);
				return ;
			}
		}
		for(auto y:g[x]) {
          
   
			vis[y]=0;
			pre[y]=x;
		}
	}
	printf("NO
");
}
int main() {
          
   
	scanf("%d",&T);
	while(T--) {
          
   
		scanf("%d",&n);
		for(int i=1;i<=n;i++) {
          
   
			scanf("%d",&a[i].k);g[i].clear();a[i].id=i;
			for(int j=1;j<=a[i].k;j++) {
          
   
				int x; scanf("%d",&x);
				g[i].push_back(x);
			}
		}
		sort(a+1,a+1+n);
		memset(vis,0,sizeof vis),memset(pre,0,sizeof pre),memset(Rec,0,sizeof Rec);
		check();
	}
}