自动搬运

查看原文

来自洛谷，原作者为

	欧鹰 我就是我，不一样的烟火

搬运于2025-08-24 21:37:28，当前版本为作者最后更新于2019-09-05 21:59:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第三篇题解 ，心态有点稳啦。正如就如上一篇题解所说，我欧鹰就是跳下去，也绝对不会给我博客打广告 真香

下面进入这道题的题解

说实话，第一次看到这题。啊！一道蓝题，吓得我加了收藏，就退了出来。做了道紫题，现在闲着无聊就又回来看这题，看了题，又看了数据，这道题真是符合他的标签，水一样颜色的题，简称为水题。

这个题其实就是，从最少人的课程开始遍历，依次递增，在再本课程的人里边选一个人，他可以选的课程最多，并他没有选其他科，就选这个人。

明明标签是图论，但我却写得像贪心，所以欢迎大家HACK！！！！！

下面是代码（代码就不解释啦，不懂得可以私聊，顺便点个赞，谢谢。）

#include<bits/stdc++.h>

using namespace std;

int t,p,n,cnt,vis[100500],head[400500],out[100500],flag;

struct nod{
	int u,v;
}a[100500];

void add(int u,int v)
{
	a[++cnt].u=head[u];
	
	head[u]=cnt;
	
	a[cnt].v=v;
}

int read(){
    char ch=getchar(); int f=1,a=0;
    while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); }
    while(isdigit(ch)){ a=a*10+ch-'0';     ch=getchar(); }
    return a*f;
}

struct node{
	int cla,num;
}in[100500];

bool cmp(node a,node b)
{
	return a.num<b.num;
}

int main()
{
	t=read();
	
	while(t--)
	{
		memset(in,0,sizeof(in));
		
		memset(out,0,sizeof(out));
		
		memset(head,0,sizeof(head));
		
		memset(vis,0,sizeof(vis));
		
		memset(a,0,sizeof(a));
		
		cnt=flag=0;
		
		p=read();
		
		n=read();
		
		for(int i=1;i<=p;i++)
		{
			//int num;
			
			in[i].num=read();
			
			int numm=in[i].num;
			
			in[i].cla=i;
			
			while(numm--)
			{
				int y;
				
				y=read();
				
				add(i,y+p);
				
				out[y+p]++;
			}
		}
		
		sort(in+1,in+1+p,cmp);
		
		for(int i=1;i<=p;i++)
		{
			int maxv=21475622,vv=-1;
			
			for(int j=head[in[i].cla];j;j=a[j].u)
			{
				int v=a[j].v;
				
				if(out[v]<maxv&&vis[v]!=1)
				{
					maxv=out[v];
					
					vv=v;
				}
			}
			
			if(vv==-1)
			{
				cout<<"NO"<<'\n';
				
				flag=1;
				
				break;
			}
			
			vis[vv]=1;
		}
		
		if(flag==0) cout<<"YES"<<'\n';
	}
	
	return 0;
	
}