更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19369035

思路

那么，相当于每个党派的两个代表就是两种情况，然后直接按其说的厌恶的关系建边跑 $\text{2 - SAT}$ 即可。

每个党派 $i$ 对应2-SAT的一个布尔变量，其两个代表 $2i$、$2i+1$ 分别对应「变量为真」「变量为假」，题目中“代表a和b互相厌恶” $\to$ 约束：**不能同时选 a 和 b**，即选 a 则必须选 b 的对立代表，选 b 则必须选 a 的对立代表。

先将代表编号转为 $0$ 起始（$a \rightarrow a - 1$），记a对应节点 $u$，b 对应节点 $v$；

互斥约束转化为两条有向边：

 1. $u \rightarrow v \oplus 1$（选 a → 必须选 b 的对立代表）

 2. $v \rightarrow u \oplus 1$（选 b → 必须选 a 的对立代表）

 （$\oplus 1$ 是异或操作，可快速找到每个代表的“对立代表”：偶数变奇数，奇数变偶数）。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 16005;
int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
int S[MAXN], c = 0;

inline int get_id(int x) {
    x--;
    return x;
}

bool dfs(int u) {
    if (vis[u ^ 1]) return false;
    if (vis[u]) return true;
    vis[u] = true;
    S[c++] = u;
    for (int v : g[u]) {
        if (!dfs(v)) return false;
    }
    return true;
}

bool Two_SAT() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            c = 0;
            if (!dfs(i)) {
                while (c > 0) vis[S[--c]] = false;
                if (!dfs(i + 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int u = get_id(a);
        int v = get_id(b);
        g[u].push_back(v ^ 1);
        g[v].push_back(u ^ 1);
    }

    if (!Two_SAT()) {
        cout << "NIE" << endl;
    } else {
        vector<int> ans;
        for (int i = 0; i < 2 * n; i += 2) {
            if (vis[i]) {
                ans.push_back(i + 1);
            } else {
                ans.push_back(i + 2);
            }
        }
        sort(ans.begin(), ans.end());
        for (int x : ans) {
            cout << x << endl;
        }
    }

    return 0;
}