HDU 1814 Peaceful Commission (2-SAT染色法+字典序最小解)

题意：委员会必须满足下列条件：每个党派都在委员会中恰有1个代表；如果2个代表彼此厌恶，则他们不能都被选入委员会。每个党在议会中有2个代表。代表从1编号到2n。 编号为2i-1和2i的代表属于第i个党派。请计算决定建立和平委员会是否可能，并输出字典序最小的一个。

题解：2-SAT染色法+字典序最小解

2-SAT问题：给出 n n n个集合，每个集合有两个元素，已知若干个 < u , v > <u, v> <u,v>，表示 u u u与 v v v矛盾（其中 u u u与 v v v属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 n n n个两两不矛盾的元素。

对于字典序最小的解，我们一般采用暴力染色法。

就是沿着图上一条路径，如果一个点被选择了，那么这条路径以后的点都将被选择；出现不可行的情况就是，存在一个集合中两者都被选择了。

注意点编号要从0开始，方便我们找他同集合的另一个。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;

//染色法（可以得到字典序最小的解）
const int MAXN = 20020;
const int MAXM = 100010;
struct Edge {
    int to, next;
}edge[MAXM];
int head[MAXN], tot;
void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v) {
    edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;
}
bool vis[MAXN];//染色标记，为 true 表示选择
int S[MAXN], top;//栈
bool dfs(int u) {
    if (vis[u ^ 1])return false;
    if (vis[u])return true;
    vis[u] = true;
    S[top++] = u;
    for (int i = head[u]; ~i; i = edge[i].next)
        if (!dfs(edge[i].to))
            return false;
    return true;
}
bool Twosat(int n) {
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < n; i += 2) {
        if (vis[i] || vis[i ^ 1])continue;
        top = 0;
        if (!dfs(i)) {
            while (top) vis[S[--top]] = false;
            if (!dfs(i ^ 1)) return false;
        }
    }
    return true;
}
int n, m, u, v;
int main() {
    while (~scanf("%d%d", &n, &m)) {
        init();
        while (m--) {
            scanf("%d%d", &u, &v);
            u--; v--;               //从0开始 ^才有意义
            addedge(u, v ^ 1);      //u和v矛盾，u与v同党派的另一个人相连
            addedge(v, u ^ 1);
        }
        if (Twosat(2 * n)) {
            for (int i = 0; i < 2 * n; i++)
                if (vis[i])
                    printf("%d\n", i + 1);
        }
        else printf("NIE\n");
    }
    return 0;
}