Codeforces Round #441 (Div. 2, by Moscow Team Olympiad) E. National Property (2-SAT問題)

第一次接觸2-sat，突然感覺自己學的離散數學和一些數學中關于邏輯的東西有了用處，開始我在做這個題的時候，我在想應該怎麼做呢，如果能有一個判斷邏輯的算法，而且能直接算出他們的解或者推翻自己的邏輯輸出錯誤，那該有多好。賽後題解就發現了2-sat。我卻有懶得要命，隻想會用，連原理都不想弄通，多嘲諷啊。即将去比賽是理由？

【題意】對于一個數字如3,那麼3'<3,且加了'的數均小于沒有加'的數，對于兩個加了'的數，按照沒有'時的規則比較大小，問存不存在一種修改方案将給定的一系列打次化為字典序遞增的。

建圖：令上一個大小為a，這一個大小為b，如果a>b 肯定讓a變為a‘ 但是b’也要和b連一條線，以免後面讓b變為b’。如果a<b  a要和b連一條線 a’和b’也要連一條線，以免後面會有b和a連線。也是一條邏輯。

#include <bits/stdc++.h>
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define mp make_pair
using namespace std;
const int N = 2e5+50;;
const int M = 2e5+50;
vector<int>vec[N],ans;
struct Edge {
    int to,next;
} edge[M];
int head[M],tot;
void init() {
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v) {
    //printf("!!!%d %d\n",u,v);
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
bool vis[N];//染色标記，為true表示選擇
int S[N],top;//棧
bool dfs(int u) {
    if(vis[u^1])return false;
    if(vis[u])return true;
    vis[u] = true;
    S[top++] = u;
    for(int i = head[u]; i != -1; i = edge[i].next)
        if(!dfs(edge[i].to))
            return false;
    return true;
}
bool Twosat(int n) {
    memset(vis,false,sizeof(vis));
    for(int i = 0; i < n; i += 2) {
        if(vis[i] || vis[i^1])continue;
        top = 0;
        if(!dfs(i)) {
            while(top)vis[S[--top]] = false;
            if(!dfs(i^1)) return false;
        }
    }
    return true;
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    init();
    for(int i=1,s,x;i<=n;i++){
        scanf("%d",&s);
        while(s--){
            scanf("%d",&x);
            vec[i].pb(x);
        }
        if(i==1)continue;
        int len=min(vec[i].size(),vec[i-1].size());
        int pos=-1;
        for(int j=0;j<len;j++){
            if(vec[i][j]!=vec[i-1][j]){
                pos=j;break;
            }
        }
        if(pos==-1){
            if(vec[i-1].size()>vec[i].size()){
                return puts("No")*0;
            }
        }
        else {
            int a=vec[i-1][pos],b=vec[i][pos];
            if(a>b){
                addedge(2*a-1,2*a-2);
                addedge(2*b-2,2*b-1);
            }
            else {
                addedge(2*a-1,2*b-1);
                addedge(2*b-2,2*a-2);
            }
        }
    }
    if(Twosat(2*m)) {
        puts("Yes");
        for(int i = 0; i < 2*m; i+=2)
            if(vis[i])
                ans.pb((i)/2+1);
       printf("%d\n",ans.size());
       for(int x : ans)printf("%d ",x);
    } else printf("No\n");
    return 0;
}