LOJ-10097（2-sat问题）

题目链接：传送门

思路：

2-sat问题，如果选每个集合最多有两个元素，eg：（Ai，Ai’），（Bi，Bi’）；

如果Ai，Bi冲突，就只能选Ai，Bi’（建立边），然后缩点，查找有无相同集合的点在同一个集合中。

然后将区块节点较小的先输出。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 200200;
int low[maxn],num[maxn],tot,co[maxn],col;
int st[maxn],top;
int fa[maxn],vis[maxn];
int head[maxn],ver[maxn],next[maxn],tim;
int MIN(int x,int y)
{
    return x<y?x:y;
}
void Init()
{
    memset(fa,0,sizeof(fa));
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
    top=0;tot=0;col=0;tim=0;
}
void addedge(int u,int v)
{
    ver[++tot]=v;next[tot]=head[u];head[u]=tot;
}
void Tarjan(int u)
{
    low[u]=num[u]=++tim;
    st[++top]=u;
    for(int i=head[u];i;i=next[i]){
        int v=ver[i];
        if(!num[v]){
            Tarjan(v);
            low[u]=MIN(low[u],low[v]);
        }
        else if(!co[v]) low[u]=MIN(low[u],num[v]);
    }
    if(low[u]==num[u]){
        col++;
        co[u]=col;
        while(st[top]!=u){
            co[st[top]]=col;
            top--;
        }
        top--;
    }
}
int main(void)
{
    int i,j,m,n,x,y;
    while(~scanf("%d%d",&n,&m)){
        Init();
        for(i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            addedge(x,(y%2==0?y-1:y+1));
            addedge(y,(x%2==0?x-1:x+1));
        }
        for(i=1;i<=n*2;i++)
        if(!num[i]) Tarjan(i);
        
        int fg=0;
        for(i=1;i<=n*2;i+=2){
            if(co[i]==co[i+1]){
                printf("NIE
");fg=1;break;
            }
            fa[i]=i+1;fa[i+1]=i;
        }
        if(fg==1) continue;
        for(i=1;i<=n*2;i++) vis[i]=(co[i]>co[fa[i]]?1:0);
        for(i=1;i<=n*2;i++){
            if(!vis[i]) printf("%d
",i);
        }
    }
    return 0;
}

View Code

参考文章：传送门