和平委员会

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1860 字
二SAT建蕴含图Tarjan缩点赋值
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1519
// 题意：n 个党派各有 2 名代表（2i - 1 与 2i），每党恰选 1 人，m 对互相厌恶的代表不能同时入选，可行则输出一种方案，否则输出 NIE。
// 思路：2-SAT。厌恶对 (a, b) 拆成 a -> !b 与 b -> !a 两条蕴含边，Tarjan 缩点后同一代表的两面在同一分量即无解，否则取分量编号较小的一面为真。
// 1. 代表编号从 1 开始，转到从 0 开始后对立面就是编号异或 1。
// 2. Tarjan 的分量编号是逆拓扑序，取编号较小的一面为真可以保证所有蕴含都被满足。
// 复杂度：O(n + m) 时间 / O(n + m) 空间
// 易错点：输出的是每个党派选中的代表编号，两面的分量编号相等时才是无解，比较大小要带上等号判断。
// 易错点：厌恶关系要拆两条边，只建一条会导致某些约束失效从而输出非法方案。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 16005;
const int MAXM = 40005;
int head[MAXN], to[MAXM], nxt[MAXM], ecnt;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
int scc[MAXN], scnt;
bool instk[MAXN];
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    instk[u] = true;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scnt++;
        while(true){
            int x = stk[top--];
            instk[x] = false;
            scc[x] = scnt;
            if(x == u) break;
        }
    }
}
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        add(a, b ^ 1);
        add(b, a ^ 1);
    }
    for(int i = 0; i < 2 * n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i = 0; i < n; i++){
        if(scc[2 * i] == scc[2 * i + 1]){
            cout << "NIE" << "\n";
            return 0;
        }
    }
    for(int i = 0; i < n; i++){
        if(scc[2 * i] < scc[2 * i + 1]) cout << 2 * i + 1 << "\n";
        else cout << 2 * i + 2 << "\n";
    }
    return 0;
}
和平委员会

正文

一本通·提高篇的其它内容
