很容易想到 \(2-sat\) 。对于每个点,不同时存在两条谎话边。

直接暴力建图要 \(O(m^2)\) ,可以用前后缀优化建图的方式完美做到限制数 \(O(n+m)\)

由于思路混乱 \(+\) 没写过,自己 \(yy\) ,导致打了好久…

具体看代码吧…

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
#include<bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;
const int maxn=400005,maxe=800005;
int n,m,N,ans[maxn],a[maxn];
int fir[maxn],nxt[maxe],son[maxe],tot;
int Tim,dfn[maxn],low[maxn],stk[maxn],top,G,blg[maxn];
bool instk[maxn];
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);
}
}
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
void add_sat(int x,int y){ add(x,y); add(y^1,x^1); }
int id(int x,int y){ return x<<1|y; } // 0坏人 1好人 0有假 1都真
int main(){
freopen("uoj210.in","r",stdin);
freopen("uoj210.out","w",stdout);
scanf("%d%d",&n,&m); N=n;
for(int i=1;i<=m;i++){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
N++;
add_sat(id(N,1),id(y,z)); // 前缀与点的关系 当前都真,则i为真 i为假,则当前有假话
if(a[x]){
add_sat(id(a[x],0),id(N,0)); // 前缀之间关系
add_sat(id(y,z^1),id(a[x],1)); // 至多一个假的限制 i为假话,则之前都为真话 之前有假话,则i为真话
}
a[x]=N;
}
for(int i=1;i<=n;i++) add_sat(id(a[i],0),id(i,0)); // 有假则是坏人, 好人则没有假
for(int i=1;i<=N;i++){
if(!dfn[id(i,0)]) Tarjan(id(i,0));
if(!dfn[id(i,1)]) Tarjan(id(i,1));
}
for(int i=1;i<=N;i++) if(blg[id(i,0)]==blg[id(i,1)]) return puts("Impossible"), 0;
for(int i=1;i<=n;i++) if(blg[id(i,0)]<blg[id(i,1)]) ans[++ans[0]]=i;
printf("%d\n",ans[0]);
for(int i=1;i<=ans[0];i++) printf("%d ",ans[i]);
return 0;
}