题意分析
显然可以跑 2-SAT。
记 $f(x)$ 为 $x$ 的同一党派的代表。
那么，若 $i,j$ 彼此厌恶，建边 $i\rightarrow f(j),j\rightarrow f(i)$ 即可。
因为 $i$ 存在，则 $j$ 不存在，$f(j)$ 存在。$j\rightarrow f(i)$ 同理。
答案即在 $2i-1,2i$ 里选择拓扑序较大的，即 SCC 编号较小的。
AC 代码
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=8000<<1;
int n;
vector<int>g[N<<2|1];
int dfn[N<<1|1],id[N<<1|1];
void Tarjan(int x){
static int cnt,low[N<<1|1];
static bool in[N<<1|1];
static vector<int>s;
dfn[x]=low[x]=++cnt;
in[x]=true;
s.push_back(x);
for(int i:g[x]){
if(!dfn[i]){
Tarjan(i);
low[x]=min(low[x],low[i]);
}else if(in[i]){
low[x]=min(low[x],dfn[i]);
}
}
if(dfn[x]==low[x]){
static int size=0;
size++;
while(s.back()!=x){
in[s.back()]=false;
id[s.back()]=size;
s.pop_back();
}
in[s.back()]=false;
id[s.back()]=size;
s.pop_back();
}
}
int f(int x){
if(x&1){
return x+1;
}else{
return x-1;
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
n*=2;
while(m--){
int i,j;
cin>>i>>j;
g[i].push_back(f(j));
g[j].push_back(f(i));
}
for(int i=1;i<=(n<<1);i++){
if(!dfn[i]){
Tarjan(i);
}
}
for(int i=1;i<=n;i+=2){
if(id[i]==id[i+1]||id[i]==id[i+n]){
cout<<"NIE\n";
return 0;
}
}
for(int i=1;i<=n;i+=2){
if(id[i]<id[i+1]){
cout<<i<<'\n';
}else{
cout<<i+1<<'\n';
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
