CF875C

思路

显然,满足 即可使整体升序。对于每个 ,都需要满足一些限制,只要所有限制前后不矛盾,则输出是。

分析 。枚举位置 为第一个两者不等的位置,有几种情况:

  • 不存在 。此时如果 ,则 ,没有额外限制。否则 一定小于 ,无解。

  • 小于 ,则 暂时小于 ,满足条件。此时只要 不改,或 同时改即可。也就是说, 如果改了, 必须改。

  • 大于 ,则 暂时大于 ,不满足条件。此时必须改 一定不能改。

由上分析,可以建图解决。

表示一定改的起点, 表示一定不改的终点。

情况 没有额外要求。情况 要求改 必须改 ,即 连边。情况 要求改 ,不改 ,即 连边, 连边。

开始搜索,如果能走到 则矛盾,否则能走到的点即为要改的点。

code

int n,m,ans;
int s,t,cur;
int a[2][maxn];
bool vis[maxn];
int head[maxn],tot;
struct nd{
	int nxt,to;
}e[maxn<<1];
void add(int u,int v){
	e[++tot]={head[u],v};
	head[u]=tot;
}
void dfs(int u){
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!vis[v]){
			dfs(v);
		}
	}
}
 
int T;
signed main(){
	//	freopen(".in","r",stdin);
	//	freopen(".out","w",stdout);
	
	n=read();m=read();
	s=0;t=m+1;
	for(int i=1;i<=n;i++){
		a[cur][0]=read();
		for(int j=1;j<=a[cur][0];j++){
			a[cur][j]=read();
		}
		if(i!=1){
			for(int j=1;j<=min(a[cur^1][0],a[cur][0]);j++){
				if(a[cur^1][j]>a[cur][j]){
					add(s,a[cur^1][j]);
					add(a[cur][j],t);
					break;
				}
				if(a[cur^1][j]<a[cur][j]){
					add(a[cur][j],a[cur^1][j]);
					break;
				}
				if(j==min(a[cur^1][0],a[cur][0])&&a[cur^1][0]>a[cur][0]){
					printf("No\n");
					return 0;
				}
			}
			
		}
		cur^=1;
	}
	dfs(s);
	if(vis[t]){
		printf("No\n");
	}
	else{
		printf("Yes\n");
		for(int i=1;i<=m;i++)if(vis[i])++ans;
		printf("%lld\n",ans);
		for(int i=1;i<=m;i++)if(vis[i])printf("%lld ",i);
	}
}