2-SAT习题讲解
Yang1208 人气:02-SAT习题讲解
讲在前面：下述例题不是按照难度顺序的，而且基本就只会讲解建图的过程。下面讲解中$A'$为$A$的反向状态。
一、bzoj习题
例一：$bzoj2199 奶牛议会$
首先我们考虑本题是$A$或$B$的问题，所以我们的建图策略为将$A'$连向$B$，表示若不选择$A$，则一定选择$B$。同样我们还需要将$B'$连向$A$。这个模型是$2-SAT$的最基本模型，由于$n$非常小，所以我们可以运用$O(n^2)$的做法来输出方案。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10010
bool vis[N];int head[N],to[N<<1],nxt[N<<1],idx,n,m;char ans[N];
void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
void dfs(int p)
{
vis[p]=true;
for(int i=head[p];i;i=nxt[i])
if(!vis[to[i]]) dfs(to[i]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;char str1[5],str2[5];
scanf("%d%s%d%s",&a,str1,&b,str2);
a=(a<<1)|(str1[0]=='Y'),b=(b<<1)|(str2[0]=='Y');
add(a^1,b),add(b^1,a);
}
for(int i=1;i<=n;i++)
{
bool is1=true,is2=true;
memset(vis,0,sizeof vis),dfs(i<<1);
for(int j=1;j<=n;j++) if(vis[j<<1]&&vis[(j<<1)|1]) {is1=false;break;}
memset(vis,0,sizeof vis),dfs((i<<1)|1);
for(int j=1;j<=n;j++) if(vis[j<<1]&&vis[(j<<1)|1]) {is2=false;break;}
if(!(is1||is2)) {printf("IMPOSSIBLE");return 0;}
if(is1&&is2) ans[i-1]='?';
else if(is1) ans[i-1]='N';
else if(is2) ans[i-1]='Y';
} ans[n]='\0',printf("%s\n",ans);
}
例二：$bzoj1997 Planet$
首先，我们按照题中给出的条件：对于给出的图满足含有一条哈密顿回路。所以我们可以将这条回路提取出来，这样我们就将问题转化为，不是哈密顿回路上的边可以放在环内，可以放在环外，问能否不相交。我们考虑边$A$和边$B$，若这两条边同时在环内相交，则同时在环外也一定相交。所以这两条就要一内一外，根据这个性质，我们可以建出$2-SAT$，$A$表示边$A$在环内，$A'$自然就表示边$A$在环外，连边方式为$A$和$B$同时在环内相交时，$A$连向$B'$，$A'$连向$B$，$B$连向$A'$，$B'$连向$A$。按照我们建出的图，验证就可以了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
struct Edge {int from,to;}edge[N];
int sta[N],top,bel[N],many,place[N];bool vis[N],in[N];
int n,m,head[N],to[N<<1],nxt[N<<1],idx,low[N],dep[N],cnt;
void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
bool check(int i,int j)
{
if(edge[i].from==edge[i].to-1) return false;
if(edge[j].from==edge[j].to-1) return false;
return (edge[j].from>edge[i].from&&edge[i].to>edge[j].from&&edge[j].to>edge[i].to)
||(edge[i].from>edge[j].from&&edge[j].to>edge[i].from&&edge[i].to>edge[j].to);
}
void init()
{
idx=cnt=many=0,memset(head,0,sizeof head);
memset(vis,0,sizeof vis),memset(bel,0,sizeof bel);
}
void tarjan(int p)
{
vis[p]=in[p]=true,dep[p]=low[p]=++cnt,sta[++top]=p;
for(int i=head[p];i;i=nxt[i])
{
if(!vis[to[i]]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
else if(in[to[i]]) low[p]=min(low[p],dep[to[i]]);
}
if(dep[p]==low[p])
{
many++;
while(sta[top+1]!=p)
bel[sta[top]]=many,in[sta[top]]=false,top--;
}
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
init(),scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) scanf("%d%d",&edge[i].from,&edge[i].to);
for(int i=1,a;i<=n;i++) scanf("%d",&a),place[a]=i;
if(m>3*n-6) {printf("NO\n");continue;}
for(int i=0;i<m;i++)
{
edge[i].from=place[edge[i].from],edge[i].to=place[edge[i].to];
if(edge[i].from>edge[i].to) swap(edge[i].from,edge[i].to);
if(edge[i].from==edge[i].to-1) continue;
for(int j=0;j<i;j++) if(check(i,j))
add(i<<1,j<<1|1),add(j<<1,i<<1|1),add(i<<1|1,j<<1),add(j<<1|1,i<<1);
} bool is=false;
for(int i=0;i<m;i++)
{
if(!vis[i<<1]) tarjan(i<<1);
if(!vis[i<<1|1]) tarjan(i<<1|1);
if(bel[i<<1]==bel[i<<1|1]) {is=true,printf("NO\n");break;}
} if(!is) printf("YES\n");
}
}
例三：$bzoj1823满汉全席$
这道题目是$A$或$B$的条件，所以我们只需要将$A'$连向$B$，$B'$连向$A$即可，当然其中说的$A$和$B$对于不一样的评委可能是不一样的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
struct Edge {int from,to;}edge[N];
int sta[N],top,bel[N],many,place[N];bool vis[N],in[N];
int n,m,head[N],to[N<<1],nxt[N<<1],idx,low[N],dep[N],cnt;
void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
bool check(int i,int j)
{
if(edge[i].from==edge[i].to-1) return false;
if(edge[j].from==edge[j].to-1) return false;
return (edge[j].from>edge[i].from&&edge[i].to>edge[j].from&&edge[j].to>edge[i].to)
||(edge[i].from>edge[j].from&&edge[j].to>edge[i].from&&edge[i].to>edge[j].to);
}
void init()
{
idx=cnt=many=0,memset(head,0,sizeof head);
memset(vis,0,sizeof vis),memset(bel,0,sizeof bel);
}
void tarjan(int p)
{
vis[p]=in[p]=true,dep[p]=low[p]=++cnt,sta[++top]=p;
for(int i=head[p];i;i=nxt[i])
{
if(!vis[to[i]]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
else if(in[to[i]]) low[p]=min(low[p],dep[to[i]]);
}
if(dep[p]==low[p])
{
many++;
while(sta[top+1]!=p)
bel[sta[top]]=many,in[sta[top]]=false,top--;
}
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
init(),scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) scanf("%d%d",&edge[i].from,&edge[i].to);
for(int i=1,a;i<=n;i++) scanf("%d",&a),place[a]=i;
if(m>3*n-6) {printf("NO\n");continue;}
for(int i=0;i<m;i++)
{
edge[i].from=place[edge[i].from],edge[i].to=place[edge[i].to];
if(edge[i].from>edge[i].to) swap(edge[i].from,edge[i].to);
if(edge[i].from==edge[i].to-1) continue;
for(int j=0;j<i;j++) if(check(i,j))
add(i<<1,j<<1|1),add(j<<1,i<<1|1),add(i<<1|1,j<<1),add(j<<1|1,i<<1);
} bool is=false;
for(int i=0;i<m;i++)
{
// if(edge[i].from==edge[i].to-1) continue;
if(!vis[i<<1]) tarjan(i<<1);
if(!vis[i<<1|1]) tarjan(i<<1|1);
if(bel[i<<1]==bel[i<<1|1]) {is=true,printf("NO\n");break;}
} if(!is) printf("YES\n");
}
}
例四：$bzoj4645 游戏$
首先，我们先考虑当$d=0$的情况。当$d=0$的时候，我们考虑实际上就是对于每一个地图，就只拥有两种选择，正好映射$A$和$A'$的两种状态。对于剩下的条件为选择$A$则必须选择$B$，两个共存的状态，所以我们只需要$A$连向$B$，$B'$连向$A'$。只需要用$2-SAT$验证下一下，并且输出一下方案就可以了。现在考虑$d\not= 0$的情况。因为$d\le 8$，所以我们可以思考一下搜索，我们枚举一下每一个地图不适合什么赛车跑，我们考虑这样的时间复杂度是$O(3^d)$的，实际上我们就只需要$O(2^d)$来完成就可以了，因为不适合$A$的时候，$B$和$C$都可以选择，不适合$B$的时候，$A$和$C$都可以选择，所以实际上还需要枚举$2$种状态，就可以枚举出来所有选择的状态。
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 200010
int dep[N],low[N],sta[N],top,bel[N],many,pos[N];
int head[N],to[N<<1],nxt[N<<1],idx,cnt,in2[N],op[N];
int head2[N],to2[N<<1],nxt2[N<<1],idx2,del[N],del2[N];
char str[N],ans[N];bool in[N],vis[N];int n,m,d,mp[3][N],us[3][N];
vector <int> v[N];queue <int> q;
void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
void add2(int a,int b) {nxt2[++idx2]=head2[a],to2[idx2]=b,head2[a]=idx2;}
void init()
{
for(int i=1;i<=many;i++) del2[i]=false,v[i].clear();
memset(dep,0,sizeof dep),memset(vis,0,sizeof vis),many=top=0;
memset(head,0,sizeof head),memset(low,0,sizeof low);
memset(head2,0,sizeof head2),memset(in2,0,sizeof in2);
memset(bel,0,sizeof bel),memset(in,0,sizeof in),idx=idx2=0;
}
void tarjan(int p)
{
vis[p]=in[p]=true;dep[p]=low[p]=++cnt,sta[++top]=p;
for(int i=head[p];i;i=nxt[i])
{
if(!vis[to[i]]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
else if(in[to[i]]) low[p]=min(low[p],dep[to[i]]);
}
if(dep[p]==low[p])
{
many++;
while(sta[top+1]!=p)
bel[sta[top]]=many,in[sta[top]]=false,top--;
}
}
void check()
{
init();
for(int i=1;i<=n;i++)
{
int a=(str[i]-'a')*n+i,b=(a-1+n)%(3*n)+1,c=(b-1+n)%(3*n)+1;
del[a]=true,op[a]=0,del[b]=del[c]=false,op[b]=c,op[c]=b;
}
for(int i=1;i<=m;i++)
{
int a=us[1][i]*n+mp[1][i],b=us[2][i]*n+mp[2][i];
if(a==b||del[a]) continue;
if(mp[1][i]==mp[2][i]||del[b]) {add(a,op[a]);continue;}
add(a,b),add(op[b],op[a]);
}
for(int i=1;i<=3*n;i++) if((!del[i])&&(!vis[i])) tarjan(i);
for(int i=1;i<=3*n;i++)
{
if(del[i]) continue;
if(bel[i]==bel[op[i]]) return;
for(int j=head[i];j;j=nxt[j])
if(bel[i]!=bel[to[j]]) add2(bel[to[j]],bel[i]),in2[bel[i]]++;
}
for(int i=1;i<=3*n;i++) if(!del[i]) v[bel[i]].push_back(i);
for(int i=1;i<=many;i++) if(in2[i]==0) q.push(i);
while(!q.empty())
{
int p=q.front();q.pop();
if(!del2[p]) for(int i=0;i<(int)v[p].size();i++)
ans[((v[p][i]-1)%n)]='A'+((v[p][i]-(v[p][i]-1)%n)/n),del2[bel[op[v[p][i]]]]=true;
for(int i=head2[p];i;i=nxt2[i])
{in2[to2[i]]--; if(!in2[to2[i]]) q.push(to2[i]);}
}ans[n]='\0',printf("%s\n",ans);
exit(0);
}
void dfs(int x)
{
if(x>d) {check();return;}
str[pos[x]]='a',dfs(x+1),str[pos[x]]='b',dfs(x+1);
}
int main()
{
scanf("%d%d%s%d",&n,&d,str+1,&m);
for(int i=1;i<=n;i++) if(str[i]=='x') pos[++pos[0]]=i;
for(int i=1;i<=m;i++)
{
char str1[3],str2[3];
scanf("%d%s%d%s",&mp[1][i],str1,&mp[2][i],str2);
us[1][i]=str1[0]-'A',us[2][i]=str2[0]-'A';
} dfs(1),printf("-1");
}
二、codeforces习题
例一：$CF875C National Property$
这道题对应的$2-SAT$中的两种状态为小写和大写。由于我们要的终止状态是从小到大，所以我们可以只考虑相邻的两个字符串，当所有的字符串相邻之间，满足前一个小于后一个的时候，所有字符串就是按照从小到大的顺序排列的了。我们考虑相邻两个字符串，因为是按照字典序排序，所以我们考虑只有第一位不相等的位置，才会对排名有所贡献，这样我们就将问题转化为对于相邻的两位，我们怎么选择。假设我们现在要考虑这样的两位：$last_i$，$now_i$，分别为上一个字符串的第$i$位，和当前字符串的第$i$位。分为两种情况：第一种情况：$last_i\lt now_i$，这样我们就有当$last_i$为大写的时候，$now_i$一定大写，$last_i$为小写的时候，$now_i$一定小写。第二种情况：$now_i\lt last_i$，这样我们就有当$now_i$一定为大写，$last_i$一定为小写。按照上述建图，跑$2-SAT$就可以了。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200010
int head[N],to[N<<1],nxt[N<<1],idx,bel[N],low[N],dep[N],sta[N],top,n,a[N],last[N],len,many,m,cnt; bool in[N];
void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
void tarjan(int p)
{
dep[p]=low[p]=++cnt,sta[++top]=p,in[p]=true;
for(int i=head[p];i;i=nxt[i])
if(!dep[to[i]]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
else if(in[to[i]]) low[p]=min(low[p],dep[to[i]]);
if(low[p]==dep[p])
{
++many;
while(sta[top+1]!=p) bel[sta[top]]=many,in[sta[top]]=false,top--;
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1,t;i<=m;i++)
{
scanf("%d",&t);
for(int j=1;j<=t;j++) scanf("%d",&a[j]);
for(int j=1;j<=min(len,t);j++)
if(last[j]<a[j]) {add(a[j],last[j]),add(last[j]+n,a[j]+n);break;}
else if(last[j]>a[j]) {add(last[j]+n,last[j]),add(a[j],a[j]+n);break;}
else if(j==min(len,t)&&len>t) {printf("No\n");return 0;}
len=t; for(int j=1;j<=len;j++) last[j]=a[j];
}
for(int i=1;i<=2*n;i++) if(!dep[i]) tarjan(i);
for(int i=1;i<=n;i++) if(bel[i]==bel[i+n]) printf("No\n"),exit(0);
printf("Yes\n"); int ans=0;
for(int i=1;i<=n;i++) if(bel[i]<bel[i+n]) ans++;
printf("%d\n",ans);
for(int i=1;i<=n;i++) if(bel[i]<bel[i+n]) printf("%d ",i);
}
例二：$CF27D Ring Rode 2$
我们考虑这道题目和$bzoj1997$的相似性，就是除了多了一个输出方案之外，没有什么区别，我们考虑输出方案，其实不需要运用$Tarjan$的知识，因为我们考虑这里的$n$很小，所以我们可以运用$dfs$，来验证与搜索答案，时间复杂度$O(n^2)$，十分优秀。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
int a[N],b[N],col[N],n,m; bool flag,vis[N];
void dfs(int p,int coll)
{
if(!vis[p])
{
col[p]=coll,vis[p]=true;
for(int i=1;i<=m;i++) if(a[i]!=a[p]&&b[i]!=b[p])
if((a[p]<a[i]&&b[p]>a[i]&&b[p]<b[i])||(a[i]<a[p]&&b[i]>a[p]&&b[i]<b[p]))
dfs(i,coll^1);
}
else if(coll!=col[p]) flag=true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i],&b[i]),a[i]--,b[i]--;
if(a[i]>b[i]) a[i]^=b[i],b[i]^=a[i],a[i]^=b[i];
}
for(int i=1;i<=m;i++) if(!vis[i]) dfs(i,0);
if(flag) printf("Impossible\n"),exit(0);
for(int i=1;i<=m;i++) printf(col[i]?"i":"o");
}
例三：$CF568CNewLanguage$
我们考虑最后答案的形式，一定是一个给出的字符串的前缀，加上一个自己安排的后缀，两者相拼接，所以我们枚举前缀，然后用$2-SAT$进行判断是否合法，然后我们考虑将剩下的位，贪心的放置，并判断是否合法。对于剩下的位，我们也可以运用$2-SAT$判断合法性，由于给出的条件为，有$A$则$B$，所以我们建边的思路为$A$连向$B$，$B'$连向$A’$。具体请见代码。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 200010
vector <int> point; bool all_flag,vis[N],in[N],mark[N];
char str[N],str2[N],ans[N],kind[2][10]; int n,m,dep[N],low[N],cnt,many,sta[N],top,head[N],to[N<<1],nxt[N<<1],idx,bel[N];
void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
void tarjan(int p)
{
dep[p]=low[p]=++cnt,vis[p]=in[p]=true,sta[++top]=p;
for(int i=head[p];i;i=nxt[i])
if(!vis[to[i]]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
else if(in[to[i]]) low[p]=min(low[p],dep[to[i]]);
if(low[p]==dep[p])
{
many++;
while(sta[top+1]!=p)
bel[sta[top]]=many,in[sta[top]]=false,top--;
}
}
void dfs(int p)
{
if(vis[p^1]) all_flag=false; vis[p]=true,point.push_back(p);
for(int i=head[p];i;i=nxt[i]) if(!vis[to[i]]) dfs(to[i]);
}
int main()
{
scanf("%s%d%d",str,&n,&m);
for(int i=1,a,b;i<=m;i++)
{
scanf("%d%s%d%s",&a,kind[0],&b,kind[1]);
add((a<<1)|(kind[0][0]=='V'),(b<<1)|(kind[1][0]=='V'));
add((b<<1)|(kind[1][0]!='V'),(a<<1)|(kind[0][0]!='V'));
} scanf("%s",str2+1);
bool flag=false;
for(int i=2;i<=2*n+1;i++) if(!vis[i]) tarjan(i);
for(int i=1;i<=n;i++) if(bel[i*2]==bel[i*2+1]&&!mark[bel[i*2]]) mark[bel[i*2]]=true;
for(int i=1;i<=n;i++) if(mark[bel[i*2+(str[str2[i]-'a']=='V')]]) {flag=true;break;}
for(int i=1;i<=2*n+1;i++) vis[i]=false;
for(int i=1;i<=n;i++)
{
if(vis[i*2+(str[str2[i]-'a']!='V')]) {flag=true;break;}
if(!vis[i*2+(str[str2[i]-'a']=='V')]) dfs(i*2+(str[str2[i]-'a']=='V'));
for(int j=1;j<=n;j++) if(vis[2*j]&&vis[2*j+1]) {flag=true;}
}
if(!flag) printf("%s\n",str2+1),exit(0);
for(int i=n;i;i--)
{
for(int j=2;j<=2*n+1;j++) vis[j]=false;
bool flag2=false;
for(int j=1;j<i;j++) if(mark[bel[j*2+(str[str2[j]-'a']=='V')]]) {flag2=true;break;}
for(int j=1;j<i;j++)
{
if(vis[j*2+(str[str2[j]-'a']!='V')]) {flag2=true;break;}
if(!vis[j*2+(str[str2[j]-'a']=='V')]) all_flag=true,dfs(j*2+(str[str2[j]-'a']=='V'));
if(!all_flag) {flag2=true;break;}
}
if(flag2) continue;
for(int j=1;j<i;j++) ans[j]=str2[j];
int flag3=0;
for(int j=str2[i]-'a'+1;j<(int)strlen(str);j++)
{
if(vis[i*2+(str[j]!='V')]||mark[bel[i*2+(str[j]=='V')]]) continue;
if(!vis[i*2+(str[j]=='V')]) all_flag=true,point.clear(),dfs(i*2+(str[j]=='V'));
if(!all_flag) {for(int k=0;k<(int)point.size();k++) vis[point[k]]=false;continue;}
flag3=j;break;
}
if(!flag3) continue; ans[i]='a'+flag3;
for(int j=i+1;j<=n;j++)
{
int flag4=-1;
for(int k=0;k<(int)strlen(str);k++)
{
all_flag=true;
if(vis[j*2+(str[k]!='V')]||mark[bel[j*2+(str[k]=='V')]]) continue;
if(!vis[j*2+(str[k]=='V')]) all_flag=true,point.clear(),dfs(j*2+(str[k]=='V'));
if(!all_flag) {for(int t=0;t<(int)point.size();t++) vis[point[t]]=false;continue;}
flag4=k;break;
}
if(flag4==-1) {flag3=0;break;} ans[j]='a'+flag4;
}
if(flag3) printf("%s\n",ans+1),exit(0);
}
printf("-1\n");
}
例五：$CF1215F Radio Stations $
首先，我们先考虑对于没有$f$的弱化版，显然直接上裸的$2-SAT$。我们现在考虑$f$，我们可以枚举每一个$f$，然后对于每一个$f$都找到能选择的电视台，然后做$2-SAT$。但是这样时间复杂度十分不乐观，所以我们考虑加点，我们将$f$加到图中，对于代表频率$i$的点，表示$f>=i$，所以对于这些频率之间，就要$i$连向$i-1$，当然，由于我们是在$2-SAT$中，所以我们还要设出频率$i$的不选点，当然在后面我们也有用，对于一个电视台，我们将他连向频率$l$的选择点，要将频率$r+1$的不选择点连向他。这样我们直接跑$2-SAT$就好了。具体的按照代码理解就好。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2000010
int head[N],to[N<<1],nxt[N<<1],idx,sta[N],top,cnt,dep[N],low[N],bel[N],many,ans[N],n,all,p,M,m; bool vis[N],in[N];
void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
void tarjan(int p)
{
dep[p]=low[p]=++cnt,sta[++top]=p,vis[p]=in[p]=true;
for(int i=head[p];i;i=nxt[i])
if(!vis[to[i]]) tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
else if(in[to[i]]) low[p]=min(low[p],dep[to[i]]);
if(dep[p]==low[p])
{
++many;
while(sta[top+1]!=p) bel[sta[top]]=many,in[sta[top]]=false,top--;
}
}
int main()
{
scanf("%d%d%d%d",&all,&p,&M,&m),n=p+M;
for(int i=1,x,y;i<=all;i++) scanf("%d%d",&x,&y),add(x+n,y),add(y+n,x);
for(int i=1,l,r;i<=p;i++)
{
scanf("%d%d",&l,&r),add(i,l+p),add(l+n+p,i+n);
if(r+1<=M) add(i,r+1+n+p),add(r+1+p,i+n);
}
for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),add(x,y+n),add(y,x+n);
for(int i=2;i<=M;i++) add(i+p,i-1+p),add(i+p-1+n,i+p+n);
for(int i=1;i<=2*n;i++) if(!vis[i]) tarjan(i);
for(int i=1;i<=n;i++) if(bel[i]==bel[i+n]) printf("-1\n"),exit(0);
for(int i=1;i<=p;i++) if(bel[i]<bel[i+n]) ans[++ans[0]]=i;
for(int i=M;i;i--) if(bel[i+p]<bel[i+p+n]) {ans[++ans[0]]=i;break;}
printf("%d %d\n",ans[0]-1,ans[ans[0]]);
for(int i=1;i<ans[0];i++) printf("%d ",ans[i]);
}
加载全部内容