[2-SAT] Codeforces #876E. National Property

考虑相邻两个串，找到第一个不同的位置，可以发现，只有这一位能决定其大小关系，因为之前的每位怎么变都相等。
两种情况：当 $st_{i,j}>st_{i+1,j}$，则 $st_{i,j}$一定变大写。 则 $st_{i,j}$一定不变。当 $st_{i,j}<st_{i+1,j}$，若 $st_{i,j}$不变，$st_{i+1,j}$一定也不变，若 $st_{i+1,j}$变了，则 $st_{i+1,j}$也要变。
直接上裸的 $2$-$sat$就好了。

关于 $2$-$sat$输出任意方案，可以一句话解决，看 mancherydalao的blog

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=400005,maxe=800005;
vector<int> st[maxn];
int n,m,len[maxn];
int fir[maxn],nxt[maxe],son[maxe],tot,ans[maxn];
int dfn[maxn],low[maxn],Tim,stk[maxn],top,G,blg[maxn];
bool instk[maxn];
void add(int x,int y){
    son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
void Tarjan(int x){
    dfn[x]=low[x]=++Tim; stk[++top]=x; instk[x]=true;
    for(int j=fir[x];j;j=nxt[j]){
        if(!dfn[son[j]]) Tarjan(son[j]), low[x]=min(low[x],low[son[j]]); else
        if(instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
    }
    if(dfn[x]==low[x]){
        G++; 
        do{
            blg[stk[top]]=G;
            instk[stk[top]]=false;
        }while(stk[top--]!=x);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&len[i]);
        for(int j=1;j<=len[i];j++){
            int x; scanf("%d",&x);
            st[i].push_back(x); 
        }
    }
    for(int i=1;i<=n-1;i++){
        int pos=-1;
        for(int j=0;j<min(len[i],len[i+1]);j++) if(st[i][j]!=st[i+1][j]){ pos=j; break; }
        if(pos==-1){
            if(st[i].size()<=st[i+1].size()) continue; else return printf("No\n"),0; 
        }
        if(st[i][pos]>st[i+1][pos]){ // x:   x<<1:没变  x<<1|1：变大写
            add(st[i][pos]<<1,st[i][pos]<<1|1);
            add(st[i+1][pos]<<1|1,st[i+1][pos]<<1); 
        } else{
            add(st[i+1][pos]<<1|1,st[i][pos]<<1|1);
            add(st[i][pos]<<1,st[i+1][pos]<<1);
        }
    }
    for(int i=2;i<=m*2+1;i++) if(!dfn[i]) Tarjan(i);
    for(int i=2;i<=m*2+1;i+=2) if(blg[i]==blg[i^1]) return printf("No\n"),0; else ans[i>>1]=blg[i]<blg[i+1]?i:i+1;
    printf("Yes\n");
    int cnt=0; for(int i=1;i<=m;i++) if(ans[i]==(i<<1|1)) cnt++;
    printf("%d\n",cnt);
    for(int i=1;i<=m;i++) if(ans[i]==(i<<1|1)) printf("%d ",i);
    return 0;
}