题目大意：
给定N个数列，数字的范围是1-m，想通过操作使得n个数列是字典序不降的。
操作如下：可以取某个数字x，使得n个数列里的x全部变成大写。
数字间的大小比较是这样的： 大小比所有的小写都要小，如果大小写相同，按照数字大小比较。
求一种可行的改变方案，使得n个数列是字典树不降的。
题目分析：
先考虑一维的情况，如果是n个长度是1的数列，那么如果ai > ai + 1，那么出现矛盾，就要令ai变成大写，然后看是否出现矛盾，然后L维是同样的情况，也就是考虑有没有矛盾关系出现。
发现每个点v的状态只有小写和大写，也就是把每个点拆成v和v'，然后建边。
如果 ai > ai + 1， 那么如果ai必定是大写，ai+1必定是小写，建边ai -> ai‘，ai + 1 -> a i +1'。
如果ai < ai + 1，那么如果ai + 1是大写，ai必定是大写；如果ai是小写，ai + 1必定是小写，建边ai + 1' -> ai，ai -> a i + 1。
然后用Tarjan+Scc缩点，topsort求出一组可行解输出即可。
(注意字典序不降，也就是如果发现 ai < ai + 1, ai > a i + 1 后就不需要向后比较了，因为更改后字典序已经大于了。
1 #include<bits/stdc++.h> 2 #define maxn 200010 3 #define pb push_back 4 using namespace std; 5 const int MAXN = 201000; 6 const int MAXM = 200010; 7 struct Edge 8 { 9 int to,next; 10 }edge[MAXM]; 11 int head[MAXN],tot; 12 void init(){ 13 tot = 0; 14 memset(head,-1,sizeof(head)); 15 } 16 void addedge(int u,int v){ 17 edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; 18 } 19 int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值1~scc 20 int Index,top; 21 int scc; 22 bool Instack[MAXN]; 23 int num[MAXN]; 24 void Tarjan(int u){ 25 int v; 26 Low[u] = DFN[u] = ++Index; 27 Stack[top++] = u; 28 Instack[u] = true; 29 for(int i = head[u]; i != -1; i = edge[i].next){ 30 v = edge[i].to; 31 if( !DFN[v] ){ 32 Tarjan(v); 33 if(Low[u] > Low[v])Low[u] = Low[v]; 34 } 35 else if(Instack[v] && Low[u] > DFN[v]) 36 Low[u] = DFN[v]; 37 } 38 if(Low[u] == DFN[u]){ 39 scc++; 40 do{ 41 v = Stack[--top]; 42 Instack[v] = false; 43 Belong[v] = scc; 44 num[scc]++; 45 } 46 while(v != u); 47 } 48 } 49 bool solvable(int n)//n是总个数,需要选择一半 50 { 51 memset(DFN,0,sizeof(DFN)); 52 memset(Instack,false,sizeof(Instack)); 53 memset(num,0,sizeof(num)); 54 Index = scc = top = 0; 55 for(int i = 0;i < n;i++) 56 if(!DFN[i]) 57 Tarjan(i); 58 for(int i = 0;i < n;i += 2){ 59 if(Belong[i] == Belong[i^1]) 60 return false; 61 } 62 return true; 63 } 64 //************************************************* 65 //拓扑排序求任意一组解部分 66 queue<int>q1,q2; 67 vector<vector<int> > dag;//缩点后的逆向DAG图 68 char color[MAXN];//染色，为'R'是选择的 69 int indeg[MAXN];//入度 70 int cf[MAXN]; 71 void solve(int n){ 72 dag.assign(scc+1,vector<int>()); 73 memset(indeg,0,sizeof(indeg)); 74 memset(color,0,sizeof(color)); 75 for(int u = 0; u < n; u++) 76 for(int i = head[u]; i != -1; i = edge[i].next){ 77 int v = edge[i].to; 78 if(Belong[u] != Belong[v]){ 79 dag[Belong[v]].push_back(Belong[u]); 80 indeg[Belong[u]]++; 81 } 82 } 83 for(int i = 0; i < n; i += 2){ 84 cf[Belong[i]] = Belong[i^1]; 85 cf[Belong[i^1]] = Belong[i]; 86 } 87 while(!q1.empty())q1.pop(); 88 while(!q2.empty())q2.pop(); 89 for(int i = 1;i <= scc;i++) 90 if(indeg[i] == 0) 91 q1.push(i); 92 while(!q1.empty()){ 93 int u = q1.front(); 94 q1.pop(); 95 if(color[u] == 0){ 96 color[u] = 'R'; 97 color[cf[u]] = 'B'; 98 } 99 int sz = dag[u].size(); 100 for(int i = 0;i < sz;i++){ 101 indeg[dag[u][i]]--; 102 if(indeg[dag[u][i]] == 0) 103 q1.push(dag[u][i]); 104 } 105 } 106 } 107 bool vis[maxn]; 108 int len; 109 vector<int> G[maxn]; 110 int main(){ 111 int n, m, l, x; 112 init(); 113 cin >> n >> m; 114 for(int i = 1; i <= n; i ++){ 115 scanf("%d",&l); 116 len = max(len, l); 117 for(int j = 1; j <= l; j ++){ 118 scanf("%d",&x); 119 x --; 120 G[i].pb(x); 121 } 122 } 123 int u, v; 124 for(int i = 2; i <= n; i ++){ 125 for(int j = 0; j < G[i].size(); j ++){ 126 if(vis[i] || j >= G[i - 1].size()) continue; 127 u = 2 * G[i][j], v = 2 * G[i - 1][j]; 128 if(u < v){ 129 vis[i] = true; 130 addedge(v, v ^ 1); 131 addedge(u ^ 1, u); 132 } 133 else if(u > v){ 134 vis[i] = true; 135 addedge(u ^ 1, v ^ 1); 136 addedge(v, u); 137 } 138 if(j == G[i].size() - 1 && !vis[i] && G[i].size() < G[i - 1].size()){ 139 cout << "No"; 140 return 0; 141 } 142 } 143 } 144 queue<int>Q; 145 if(solvable(2*m)){ 146 solve(2*m); 147 cout << "Yes" << endl; 148 for(int i = 0; i < m; i ++){ 149 if(color[Belong[(2*i) ^ 1] ] == 'R') Q.push(i + 1); 150 } 151 cout << Q.size() << endl; 152 while(!Q.empty()){ 153 printf("%d ",Q.front()); 154 Q.pop(); 155 } 156 } 157 else{ 158 cout << "No"; 159 } 160 return 0; 161 }