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;
}