HMF-have much fun Site
文章
标签
16
联系方式戳我~
阅
【题解】P8252 讨论
热度: loading...
首先把集合按大小从大到小排序，这里给出一个推论，在于当前集合有交的集合中，如果存在满足条件的集合，则大小最小的集合一定是其中一个。
考虑反证：如果当前集合与比与他有交的最小的集合不满足条件，而与一个更大的集合满足条件，则那个更大的集合和与他有交的最小的集合一定也满足条件。但我们之所以会处理到当前集合是因为之前的集合没有满足条件的，矛盾。
记下覆盖每一个位置的最小的集合编号，每次查看与自己有交的最小集合是否满足条件即可。
#include<bits/stdc++.h>
#define N 2000010
using namespace std;
int T,n,m;
struct node{
int c,id;
vector<int> a;
void init() {c=id=0;a.clear();}
bool operator <(const node o) {return c>o.c;}
}p[N];
int bel[N],mp[N];
int read() {
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
return f*res;
}
void work() {
n=read();
for(int i=1; i<=n; i++) {
p[i].init(),bel[i]=0,p[i].c=read(),p[i].id=i;
for(int j=0; j<p[i].c; j++) p[i].a.push_back(read());
}
sort(p+1,p+n+1);int x,y;
// for(int i=1; i<=n; i++) printf("%d\n",p[i].c);
int tmp=0;
for(int i=1; i<=n; i++) {
x=y=0,tmp=p[i].id,mp[p[i].id]=i;
for(int j=0; j<p[i].c; j++) {
int t=p[i].a[j],v=bel[t];bel[t]=tmp;
if(v==0) v=tmp;
if(!x) x=v;
else if(x!=v) y=v;
if(x&&y) {n=p[i].c=-1;}
}
}
if(n!=-1) printf("NO\n");
else {
if(x==tmp||y==tmp) ;
else if(p[mp[x]].c>p[mp[y]].c) x=tmp;
else y=tmp;
printf("YES\n%d %d\n",x,y);
}
}
int main() {
T=read();
while(T--) work();
}
赏
