欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

2sat 学习资料
https://blog.csdn.net/ljw_study_in_CSDN/article/details/108896054?spm=1001.2014.3001.5506
求解最强联通分量
https://www.sohu.com/a/245954819_100201031
https://www.luogu.com.cn/blog/dzz-best-programmer/tarjan

题目大意

https://codeforces.com/contest/875/problem/C
一个数字x的大写形式用 x’表示。
比如2的大写用2‘。大写的字典序要比小写的小。
给定n个由m个数字组成的数组，改变其中几个数字的大小写，使得n个数字串从前到后按照字典序非下降排列。

分析&思路

一个数字要么大写，要么小写，直接想到思路就是用2sat表示。
为每个数字建立改变大小写标记。
$node[i\ast 2],node[i\ast 2+1]分别代表数字i要小写和大写。$

分析一下2sat建立边的过程。
对于2个数组来说，大小关系是由第1位不相同的数字决定的。
假设2个数组A, B(位置关系，A在B前面)第1位不同的下标为j。
有以下4种情况。
1, 2是分析A[j]==B[j]的情况

1. A.size == j 说明A, B前j位都相同，且A已经比较完了，那显然B>=A的，所以无论中间数字大小怎么改变都不影响B>=A, 不需要建立边。
2. B.size ==j, 由于上面已经包含了B.size>=A.size的情况，这里只要分析A.size>B.size, 如果这个条件成立那么A>B， 此时无论数字怎么变A>B，无解。
3. A[j]<B[j], 说明本来就A<B, 如果A[j]小写推出B[j]一定小写，如果B[j]大写可以推出A[j]一定大写。
4. A[j]>B[j], 说明A>B, A[j]必须大写，B[j]必须小写。

AC代码

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>

using namespace std;


const int N = 2e5 +10;
const int E = 4e5+10;
// 边属性
class Edge {
public:
    int toVertex;
    int nextEdge;
};

// 点属性
class Node {
public:
    int head;
    int indu;
};

class Graph {
public:
    Edge edges[E];
    Node nodes[N];
    int usedEdge=0;
    Graph() {
        usedEdge = 0;
    }

    void initEdge(int n) {
        for(int i=0;i<=n;++i) {
            nodes[i].head=-1;
            nodes[i].indu  = 0;
        }
        usedEdge = 0;
    }

    void addEdge(int a, int b) {
        if(a==b) return;
        edges[usedEdge].nextEdge = nodes[a].head;
        nodes[a].head = usedEdge;
        edges[usedEdge].toVertex = b;
        nodes[b].indu++;
        usedEdge++;

        // cout<<"add edge: "<<a<<","<<b<<endl;
    }

        
    int dfn[N], low[N];
    stack<int> st;
    int deep, sum;
    int color[N];

    void initTarjan(int n) {
        deep = 0;
        sum=0;
        memset(dfn, 0,sizeof(int)*n);
        memset(low, 0,sizeof(int)*n);
        memset(color, 0,sizeof(int)*n);

    }

    void tarjan(int u) {
        dfn[u] = ++deep;
        low[u] = deep;
        st.push(u);

        for(int i=nodes[u].head;i>=0;i = edges[i].nextEdge) {
            int v = edges[i].toVertex;
            if(!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if(!color[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }

        if(dfn[u]==low[u]) {
            color[u] = ++sum;
            while(st.top()!=u) {
                int v = st.top();
                st.pop();
                color[v]=sum;
            }
            st.pop();
        }
    }

    map<int, int> loc;

    bool topo(int n, bool deb) {
        queue<int>qu;
        for(int i=1;i<=n;++i) {
            if(nodes[i].indu==0) {
                qu.push(i);
            }
        }
        int l=0;
        while(!qu.empty()) {
            int f = qu.front();
            loc[f]=++l;
            qu.pop();

            for(int i=nodes[f].head;i>=0;i=edges[i].nextEdge) {
                int v = edges[i].toVertex;
                nodes[v].indu--;
                if(nodes[v].indu==0) qu.push(v);
            }
        }

        if(deb) cout<<l<<endl;
        return l==n;
    }
};

Graph og;

// false not swap
void either(int i, bool si, int j, bool sj) {
    og.addEdge(i*2+(si^1), 2*j+sj);
    og.addEdge(j*2+(sj^1), 2*i+si);
}

void imply(int i, bool si, int j, bool sj) {
    either(i, si^1, j, sj);
}

void must(int i, bool sel) {
    og.addEdge(i*2+(sel^1), i*2+sel);    
}

vector<int> Q[N];

void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    og.initEdge(2*m);

    for(int i=0;i<n;++i) {
        int a;
        scanf("%d", &a);
        Q[i].resize(a);
        for(int j=0;j<a;++j) scanf("%d", &Q[i][j]);
    }

    for(int i=0;i<n-1;++i) {
        int j;
        for(j=0;j<Q[i].size() && j<Q[i+1].size() && Q[i][j]==Q[i+1][j];++j);
        if(j==Q[i].size())continue;
        if(j==Q[i+1].size() && Q[i].size()>Q[i+1].size()) {
            puts("No");
            return;
        }

        if(Q[i][j]<Q[i+1][j]) {
            imply(Q[i][j]-1, 0, Q[i+1][j]-1, 0);
        } else {
            must(Q[i][j]-1, 1);
            must(Q[i+1][j]-1, 0);
        }
    }
    // puts("run");

    int c = m;
    og.initTarjan(2*c);
    for(int i=0;i<2*c;++i) {
        if(!og.dfn[i])og.tarjan(i);
    }

    vector<int> ans;
    for(int i=0;i<c;++i) {
        if(og.color[2*i]==og.color[2*i+1]){
            puts("No");
            return;
        }
        if(og.color[2*i]>og.color[2*i+1]) ans.push_back(i);
    }
    puts("Yes"); 

    printf("%d\n", ans.size());
    for(int i=0;i<ans.size();++i){
        if(i)putchar(' ');
        printf("%d", ans[i]+1);
    }
    puts("");
}


int main() {
    solve();
    return 0;
}
/*

 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。