Steven_Meng's Blog

传送门

GDOI

根据$2-SAT$套路，我们要把这个问题转换成依赖性问题，即选择$u$，就必须选$v$。

这个也是非常好转化的，假设$i$，$j$互相憎恶，因为每个党派都必须有一个代表，所以选择了$i$就必须选择$j$所在的党派的另一人，同理，选择了$j$就必须选择$i$所在党派的另一人。

#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int dfn[MAXN],low[MAXN],cnt;
stack<int>stk;
int scc,col[MAXN];
void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    stk.push(u);
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (!col[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]){
        ++scc;
        do{
            col[u]=scc;
            u=stk.top(),stk.pop();
        }while (low[u]!=dfn[u]);
    }
}
inline int Other(int x){//返回x的党派的另一人
    if (x%2==0) return x-1;
    else return x+1;
}
int main(){
    int n=read(),m=read();
    for (register int i=1;i<=m;++i){
        int u=read(),v=read();
        AddEdge(u,Other(v));
        AddEdge(v,Other(u));
    }
    for (register int i=1;i<=(n<<1);++i){
        if (!dfn[i]) tarjan(i);
    }
    for (register int i=1;i<=n;++i){
        if (col[i*2-1]==col[i*2]){
            puts("NIE");
            return 0;
        }
    }
    for (register int i=1;i<=n;++i){
        int u=i*2-1,v=i*2;
        if (col[u]<col[v]) printf("%d\n",u);
        else printf("%d\n",v);
    }
}