Conspiracy

给定一张 \(n\) 个点 \(m\) 条边的无向图，你要把 \(V\) 分为 \(S\) 和 \(T = V \setminus S\) 两部分，使得 \(S, T \neq ?\)，且 \(S\) 是团而 \(T\) 是独立集。求方案数。

\(n ≤ 5000\)。

题解

首先可以观察到性质：假设我们找出来了一组 \(S,T\)，那么 \(S\) 不能拿 \(\geq 2\) 个点给 \(T\)，\(T\) 也不能拿 \(\geq 2\) 个点给 \(S\)。

所以我们可以枚举两边交换的情况，\(O(n^2)\)。

问题转化成了如何找初始时的 \(S,T\)。令 \(x_i=1,0\) 分别表示 \(i\) 在团、独立集中。那么

• \(i,j\) 有边等价于 \(x_i \lor x_j=1\)。

• \(i,j\) 无边等价于 \(x_i \land x_j=0\)。

这就是经典的2-SAT模型了。Tarjan解决即可。

CO int N=5e3+10;
int e[N][N];
vector<int> to[2*N];
int pos[2*N],low[2*N],dfn;
int stk[2*N],ins[2*N],top;
int col[2*N],idx;

void tarjan(int u){
    pos[u]=low[u]=++dfn;
    stk[++top]=u,ins[u]=1;
    for(int v:to[u]){
        if(!pos[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]) low[u]=min(low[u],pos[v]);
    }
    if(low[u]==pos[u]){
        ++idx;
        do{
            int x=stk[top];
            ins[x]=0,col[x]=idx;
        }while(stk[top--]!=u);
    }
}

vector<int> S,T;
int adj[N];

int main(){
    int n=read<int>();
    if(n==2){
        puts("2");
        return 0;
    }
    for(int i=1;i<=n;++i){
        for(int j=read<int>();j--;) e[i][read<int>()]=1;
        for(int j=1;j<=n;++j)if(j!=i){
            if(e[i][j]) to[i].push_back(j+n);
            else to[i+n].push_back(j);
        }
    }
    for(int i=1;i<=2*n;++i)if(!pos[i]) tarjan(i);
    for(int i=1;i<=n;++i){
        if(col[i]==col[i+n]){
            puts("0");
            return 0;
        }
        if(col[i]<col[i+n]) T.push_back(i);
        else S.push_back(i);
    }
    for(int u:S)for(int v:T)if(e[u][v])
        adj[u]=!adj[u]?v:-1;
    for(int u:T)for(int v:S)if(!e[u][v])
        adj[u]=!adj[u]?v:-1;
    int ans=S.size() and T.size(); // edit 1
    if(S.size()>1)for(int u:S) ans+=!adj[u];
    if(T.size()>1)for(int u:T) ans+=!adj[u];
    for(int u:S)for(int v:T)
        ans+=(!adj[u] or adj[u]==v) and (!adj[v] or adj[v]==u);
    printf("%d\n",ans);
    return 0;
}

LOJ2155 Conspiracy

原文：https://www.cnblogs.com/autoint/p/12204238.html