#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define mar(o) for(int E=fst[o];E;E=e[E].nxt)
#define v e[E].to
using namespace std;
const int n7=2012345,m7=4012345;
struct dino{int to,nxt;}e[m7];
int n,m,ecnt,fst[n7],t,cnt,col[n7];
int dfn[n7],low[n7],top,sak[n7];
bool in[n7];

int rd(){
	int shu=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))shu=(shu<<1)+(shu<<3)+ch-'0',ch=getchar();
	return shu;
}

void edge(int sta,int edn){
	ecnt++;
	e[ecnt]=(dino){edn,fst[sta]};
	fst[sta]=ecnt;
}

void tarjan(int o){
	t++,dfn[o]=low[o]=t;
	top++,sak[top]=o,in[o]=1;
	mar(o){
		if(!dfn[v]){
			tarjan(v);
			low[o]=min(low[o],low[v]);
		}
		else if(in[v])low[o]=min(low[o],low[v]);
	}
	if(dfn[o]!=low[o])return;
	cnt++;
	while(sak[top+1]!=o){
		in[ sak[top] ]=0;
		col[ sak[top] ]=cnt,top--;
	}
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n){
		edge(i*2-1,i*2+n*2),edge(i*2,i*2-1+n*2);
		edge(i*2-1+n*2,i*2),edge(i*2+n*2,i*2-1);
	}
	rep(i,1,m){
		int sta=rd(),edn=rd();
		edge(sta,edn+n*2);
		edge(edn,sta+n*2);
	}
	rep(i,1,n*4)if(!dfn[i])tarjan(i);
	rep(i,1,n*2)if(col[i]==col[i+n*2]){
		puts("NIE");return 0;
	}
	rep(i,1,n*2){
		if(col[i]>col[i+n*2])printf("%d ",i);
	}
	return 0;
}

2SAT

我的大体思路是这样的：

• 对于同一个党派的人 $x$ 和 $x+1$ ，有且仅有一个 人能参加，于是就把它们连起来

• 对于输入的憎恨人，也把他们连起来

但是最后这个代码只有28分，必须要把if(col[i]>col[i+n*2])printf("%d ",i);改成if(col[i]<col[i+n*2])printf("%d ",i); （即大于号改成小于号）才能A。但是按照常规来说应该是原先的写法才能对……不太理解，求教，感谢