题解 P5782 [POI2001] 和平委员会

我的2-SAT模板题题解

我那篇题解里介绍了 2-SAT 的内容及解决方法，这篇题解直接讲实现。

连边

如何处理题目给出的不友好的代表队？

对于题目给出的互相厌恶的 a 和 b，即要求不能使 a 和 b 处于一个连通块。记与 i 为一个党派的另一位代表为 zmz(i) （用函数实现）。则由 a 向 zmz(b) 连一条边，由 b 向 zmz(a) 连一条边。

求连通块

跑一遍 Tarjan

输出

因为连边时我们已经排除了有矛盾的代表，所以不能创立委员会现在等价于一个党派的2个代表处于一个连通块。

对于能创立委员会的情况，每个党派统一输出其连通块编号较小的那个代表。

CODE

#include <bits/stdc++.h>
using namespace std;

inline int gin(){//快读
    char c=getchar();
    int s=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

const int N=40005;
int n,m,dfn[N],low[N],dfc,st[N],top,co[N],col;
int head[N],to[N],ne[N],tot;

inline int zmz(int x){//求党派里的另一位代表
    return x&1 ? x+1 : x-1;
}

inline void add(int u,int v){//连边
    to[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}

void tarjan(int u){
    dfn[u]=low[u]=++dfc;
    st[++top]=u;
    for(int i=head[u];i;i=ne[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!co[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        co[u]=++col;
        while(st[top]!=u){
            co[st[top]]=col;
            top--;
        }
        top--;
    }
}

int main(){
    n=gin(),m=gin();
    for(int i=1;i<=m;i++){
        int u=gin(),v=gin();
        add(u,zmz(v)),add(v,zmz(u));//连边
    }
    for(int i=1;i<=n*2;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n*2;i+=2){
        if(co[i]==co[i+1]){//不能创立委员会
            puts("NIE");
            return 0;
        }
    }
    for(int i=1;i<=n*2;i+=2){
        printf("%d\n",co[i]<co[i+1] ? i : i+1);
    }
    return 0;
}